Guess the Number Using Bitwise Questions II - Video Solutions
3094. Guess the Number Using Bitwise Questions II (Leetcode Medium)
Guess the Number Using Bitwise Questions II - Video Solution
Watch 2 video solutions for Guess the Number Using Bitwise Questions II, a medium level problem involving Bit Manipulation, Interactive. This walkthrough by Programming Live with Larry has 112 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |