Skip to main content
Talentd

Guess the Number Using Bitwise Questions II - Solution & Explanation

MediumPremiumFree on FleetCodeBit ManipulationInteractive6 min read
Practice this problem

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

 

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.

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 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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force GuessingO(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

Video Solution

3094. Guess the Number Using Bitwise Questions II (Leetcode Medium) • Programming Live with Larry • 112 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Guess the Number Using Bitwise Questions II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary