Problem

There is a number n between 0 and 230 - 1 (both inclusive) that you have to find.

There is a pre-defined API int commonBits(int num) that helps you with your mission. But here is the challenge, every time you call this function, n changes in some way. But keep in mind, that you have to find the initial value ofn.

commonBits(int num) acts as follows:

  • Calculate count which is the number of bits where both n and num have the same value in that position of their binary representation.
  • n = n XOR num
  • Return count.

Return the number n.

Note: In this world, all numbers are between 0 and 230 - 1 (both inclusive), thus for counting common bits, we see only the first 30 bits of those numbers.

Constraints:

  • 0 <= n <= 230 - 1
  • 0 <= num <= 230 - 1
  • If you ask for some num out of the given range, the output wouldn’t be reliable.

Examples

Example 1

1
2
3

Input: n = 31
Output: 31
Explanation: It can be proven that it's possible to find 31 using the provided API.

Example 2

1
2
3

Input: n = 33
Output: 33
Explanation: It can be proven that it's possible to find 33 using the provided API.

Constraints

  • 0 <= n <= 2^30 - 1
  • 0 <= num <= 2^30 - 1
  • If you ask for some num out of the given range, the output wouldn’t be reliable.

Solution

Method 1 – Bitwise Simulation and XOR Reversal

Intuition

Each call to commonBits(num) both reveals information about the current n and mutates it by n = n ^ num. To recover the initial value, we can simulate the process: for each bit, query with a mask for that bit, record the result, and keep track of the cumulative XOR of all queries. After all queries, the initial value is the XOR of the final n and the cumulative XOR of all queries.

Approach

  1. For each bit position from 0 to 29:
    • Query with num = 1 << i.
    • If the result is 30, the bit in n matches the bit in num (i.e., the bit is set in n).
    • Accumulate the XOR of all queries.
  2. After all queries, the current n is the result of applying all XORs to the initial value.
  3. The initial value is the XOR of the current n and the cumulative XOR of all queries.
  4. Return the reconstructed initial value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int findNumber(ArrayReader reader) {
        int xor = 0, n = 0;
        for (int i = 0; i < 30; i++) {
            int mask = 1 << i;
            int res = reader.commonBits(mask);
            xor ^= mask;
            if (res == 30) n |= mask;
        }
        return n ^ xor;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findNumber(self, reader: 'ArrayReader') -> int:
        xor = 0
        n = 0
        for i in range(30):
            mask = 1 << i
            res = reader.commonBits(mask)
            xor ^= mask
            if res == 30:
                n |= mask
        return n ^ xor

Complexity

  • ⏰ Time complexity: O(1) — Always 30 queries, regardless of the value of n.
  • 🧺 Space complexity: O(1) — Only a few variables are used.