Since \(7 = 111_{(2)}\) is the smallest positive integer \(X\) that satisfies \(f(X) = 3\), we output -1 if \(N_i \le 6\). From now on, we assume that \(N_i \ge 7\).

Solution 1. Enumeration of all candidates

There are at most \(\displaystyle\binom{60}{3} = 34220\) positive integers less than or equal to \(10^{18}\) that have exactly \(3\) ones when represented in binary notation. (We have \(10^{18} < 2^{60}\), so \(1\) can only appear in \(60\) places below the \(2^{59}\) position.) Therefore, we can naively enumerate all of them (let’s say there are \(M\) such integers) using three nested loops, sort them, and then for each test case \(N_i\), we can find the maximum value less than or equal to \(N_i\) using binary search in \(\mathrm{O}(\log M)\) time, for a total of \(\mathrm{O}((M + T) \log M)\) time.

Sample Implementation (C, 48 ms)

(Above is a modification of a translation by GPT-4.)

(Below is a translation by GPT-4.)

Solution 2. Case distinction

When \(N_i\) is represented in binary notation,

• If there are 3 or more ones, the answer is the number with only the top 3 ones remaining.
• If there is exactly 1 one, the answer is the number with that one changed to 0 and 3 ones placed consecutively immediately below it.
• If there are exactly 2 ones,
  • If the lower one is in a position greater than or equal to \(2^2\), the answer is the number with that one changed to 0 and 2 ones placed consecutively immediately below it.
  • If the lower one is in a position less than or equal to \(2^1\), the answer is the number with both ones changed to 0 and 3 ones placed consecutively immediately below the upper one.

In any case, it is clear that the number shown above is a positive integer less than or equal to \(N_i\), and the maximality can be proven by mathematical induction. (The validity of Solution 3 is almost the same as the proof.) As a solution, we only need to check the number and position of ones, so we can answer in \(\mathrm{O}(\log N_i)\) time for each test case.

Sample Implementation (C, 45 ms)

Solution 3. Recursion

Starting with \(x = N_i\), we recursively find the answer when the input is \(x\).

• If \(f(x) = 3\), output \(x\) as the answer. (Since \(x\) satisfies the condition, the maximum value less than or equal to \(x\) that satisfies the condition is obviously \(x\) itself.)
• If \(f(x) < 3\), replace \(x\) with \(x - 1\). (Since \(x\) does not satisfy the condition, the answer is in the range less than or equal to \(x - 1\).)
• If \(f(x) > 3\), replace \(x\) with the number obtained by changing the least significant 1 in \(x\) to 0.
  Validity

  Since \(x\) does not satisfy the condition, the answer is in the range less than or equal to \(x - 1\). Furthermore, for any integer \(y\) that is strictly greater than the replaced \(x\) and less than or equal to the original \(x\), the state above the replaced digit is exactly the same, and since there is at least one 1 below the replaced digit, \(f(y) > 3\) holds. Therefore, it is not a problem to skip checking this range.

We do not need to calculate \(f(x)\) seriously except for the input and the update after the second case, and the update in the second case occurs at most 3 times (if the \(2^0\) position is 1, \(f(x)\) does not decrease, and if not, \(f(x)\) increases to at least 3 except when the \(2^1\) position is 1), so we can answer in \(\mathrm{O}(\log N_i)\) time for each test case.

Sample Implementation (C, 50 ms)

Note that in Solutions 2 and 3, if you calculate \(f(X)\) too many times, the computational complexity for each test case becomes worst-case \(\Theta((\log N_i)^2)\). However, you can still get AC if you use a fast language or implement it efficiently.