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 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 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.
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)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|