Welcome to Subscribe On Youtube
3094. Guess the Number Using Bitwise Questions II
Description
There is a number n
between 0
and 2^{30}  1
(both inclusive) that you have to find.
There is a predefined 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 bothn
andnum
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 2^{30}  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 <= 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.
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 }