# 3094. Guess the Number Using Bitwise Questions II

## Description

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 of n.

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.

Example 1:

Input: n = 31

Output: 31

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

Example 2:

Input: n = 33

Output: 33

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

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.

## Solutions

### Solution 1: Bit Manipulation

Based on the problem description, we observe that:

• If we call the commonBits function twice with the same number, the value of $n$ will not change.
• If we call commonBits(1 << i), the $i$-th bit of $n$ will be flipped, i.e., if the $i$-th bit of $n$ is $1$, it will become $0$ after the call, and vice versa.

Therefore, for each bit $i$, we can call commonBits(1 << i) twice, denoted as count1 and count2 respectively. If count1 > count2, it means the $i$-th bit of $n$ is $1$, otherwise it is $0$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$.

• /**
* Definition of commonBits API (defined in the parent class Problem).
* int commonBits(int num);
*/

public class Solution extends Problem {
public int findNumber() {
int n = 0;
for (int i = 0; i < 32; ++i) {
int count1 = commonBits(1 << i);
int count2 = commonBits(1 << i);
if (count1 > count2) {
n |= 1 << i;
}
}
return n;
}
}

• /**
* Definition of commonBits API.
* int commonBits(int num);
*/

class Solution {
public:
int findNumber() {
int n = 0;
for (int i = 0; i < 32; ++i) {
int count1 = commonBits(1 << i);
int count2 = commonBits(1 << i);
if (count1 > count2) {
n |= 1 << i;
}
}
return n;
}
};

• # Definition of commonBits API.
# def commonBits(num: int) -> int:

class Solution:
def findNumber(self) -> int:
n = 0
for i in range(32):
count1 = commonBits(1 << i)
count2 = commonBits(1 << i)
if count1 > count2:
n |= 1 << i
return n


• /**
* Definition of commonBits API.
* func commonBits(num int) int;
*/

func findNumber() (n int) {
for i := 0; i < 32; i++ {
count1 := commonBits(1 << i)
count2 := commonBits(1 << i)
if count1 > count2 {
n |= 1 << i
}
}
return
}