Problem

There is a number n that you have to find.

There is also a pre-defined API int commonSetBits(int num), which returns the number of bits where both n and num are 1 in that position of their binary representation. In other words, it returns the number of set bits in n & num, where & is the bitwise AND operator.

Return the number n.

Examples

Example 1:

1
2
3
4

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
4

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

Constraints:

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

Solution

Method 1 – Bitwise Construction by Querying Each Bit

Intuition

We can reconstruct the hidden number n by querying each bit position individually. For each bit position, we query with a number that has only that bit set. If the result is 1, then that bit is set in n; otherwise, it is not. By repeating this for all 32 bits, we can reconstruct n.

Approach

  1. Initialize ans = 0.
  2. For each bit position i from 0 to 31:
    • Query with num = 1 << i.
    • If commonSetBits(num) returns 1, set the i-th bit in ans.
  3. Return ans.

Code

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

class Solution {
public:
    int findNumber(ArrayReader &reader) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            if (reader.commonSetBits(1 << i)) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func findNumber(reader ArrayReader) int {
    ans := 0
    for i := 0; i < 32; i++ {
        if reader.commonSetBits(1 << i) == 1 {
            ans |= 1 << i
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int findNumber(ArrayReader reader) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (reader.commonSetBits(1 << i) == 1) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun findNumber(reader: ArrayReader): Int {
        var ans = 0
        for (i in 0 until 32) {
            if (reader.commonSetBits(1 shl i) == 1) {
                ans = ans or (1 shl i)
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def findNumber(self, reader: 'ArrayReader') -> int:
        ans = 0
        for i in range(32):
            if reader.commonSetBits(1 << i) == 1:
                ans |= 1 << i
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn find_number(reader: &mut ArrayReader) -> i32 {
        let mut ans = 0;
        for i in 0..32 {
            if reader.common_set_bits(1 << i) == 1 {
                ans |= 1 << i;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    findNumber(reader: ArrayReader): number {
        let ans = 0;
        for (let i = 0; i < 32; i++) {
            if (reader.commonSetBits(1 << i) === 1) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

Complexity

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