Guess the Number Using Bitwise Questions II solution and explanation
The 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 of n.
commonBits(int num) acts as follows:
- Calculate
countwhich is the number of bits where bothnandnumhave 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 - 10 <= num <= 230 - 1- If you ask for some
numout of the given range, the output wouldn't be reliable.
Approach overview
Problem Overview: A hidden integer must be determined using a limited number of interactive bitwise questions. Each query reveals information about how the unknown number behaves under a bitwise operation. The goal is to reconstruct the exact value by extracting information about each individual bit.
Approach 1: Bit-by-Bit Reconstruction (Bit Manipulation) (Time: O(log M), Space: O(1))
The key observation is that the hidden number can be determined independently bit by bit. Instead of searching the entire number space, you probe each bit position using carefully constructed masks. For every bit position i, send a query where only that bit is set. The response reveals whether the corresponding bit in the secret number contributes to the result of the bitwise operation. If the query response indicates the bit is present, set that bit in your answer; otherwise leave it unset. Iterate through all bit positions (typically up to 30 for 32‑bit integers) and assemble the final number using bitwise OR.
This works because bitwise operations isolate information about individual positions. A query mask like 1 << i isolates the i-th bit. The interactive response tells you whether the hidden number has that bit set. Building the answer incrementally avoids brute forcing the entire range and keeps the number of queries small.
Implementation is straightforward once you understand the bit logic. Maintain an integer ans. For each bit position from 0 to the maximum possible bit, construct the mask, send the query, and update ans if the response indicates a set bit. Bit shifts and OR operations make the update constant time.
This technique relies heavily on concepts from bit manipulation and common patterns used in interactive problems. Understanding how to isolate and combine bits with operations like <<, |, and masking is essential.
Recommended for interviews: The bit-by-bit reconstruction approach is the expected solution. Interviewers want to see that you recognize each bit can be determined independently and that you can design queries to isolate information. Brute forcing the number space would require too many queries, while the bitwise strategy solves the problem in O(log M) queries with constant memory.
Solution
Based on the problem description, we observe that:
- If we call the
commonBitsfunction twice with the same number, the value ofnwill not change. - If we call
commonBits(1 << i), thei-th bit ofnwill be flipped, i.e., if thei-th bit ofnis1, it will become0after 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.
# 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 (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.
* 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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Guessing | O(M) | O(1) | Conceptual baseline; impractical because interactive limits prevent testing all values |
| Bit-by-Bit Reconstruction (Bit Manipulation) | O(log M) | O(1) | Optimal solution when queries reveal bitwise behavior of the hidden number |
Frequently asked questions
Is Guess the Number Using Bitwise Questions II easy or hard?
The problem is rated Medium because the implementation is simple once the idea is clear, but the key insight is recognizing that each bit can be determined independently through queries. Candidates unfamiliar with bitwise reasoning or interactive patterns may initially find it tricky.
Guess the Number Using Bitwise Questions II Python/Java solution
The implementation is nearly identical across Python, Java, C++, and Go. Iterate through each bit position, construct a mask using a left shift, send the interactive query, and update the result using bitwise OR if the response indicates the bit is set. Each language handles bit operations efficiently, keeping the solution concise.
How to solve Guess the Number Using Bitwise Questions II in O(log n)?
Use bitwise masking to check each bit individually. Construct a query mask like (1 << i) and send it to the interactive system. The response indicates whether the hidden number contributes that bit under the defined operation. Update the answer using bitwise OR and repeat for all bit positions, resulting in O(log n) queries.
What is the best approach for Guess the Number Using Bitwise Questions II?
The optimal approach reconstructs the hidden value one bit at a time using bit manipulation. For each bit position, you send a query with a mask that isolates that bit and analyze the response. This reveals whether the bit is set in the secret number. Repeating this for all bit positions determines the full number in O(log M) queries with O(1) space.
Is Guess the Number Using Bitwise Questions II asked at Google/Amazon/Meta?
Problems involving bit manipulation and interactive queries appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the pattern of reconstructing values using bitwise operations and minimal queries is a common interview theme.
What data structure is used in Guess the Number Using Bitwise Questions II?
The solution primarily uses bit manipulation rather than complex data structures. A single integer stores the reconstructed answer, and bit masks generated with shifts (1 << i) isolate individual positions. The logic relies on bitwise operations such as OR and shifting.
What is the time complexity of Guess the Number Using Bitwise Questions II?
The optimal solution runs in O(log M) time, where M is the maximum possible value of the hidden number. Each query determines information about a single bit, and integers typically have around 30–32 relevant bits. Space complexity remains O(1) because only the reconstructed answer and temporary masks are stored.