Skip to main content
Talentd

Guess the Number Using Bitwise Questions I - Solution & Explanation

MediumPremiumFree on FleetCodeBit ManipulationInteractive5 min read
Practice this problem

Problem Statement

There is a number n that you have to find.

There is also a pre-defined API int commonSetBits(int num), which returns the number of bits where both n and num are 1 in that position of their binary representation. In other words, it returns the number of set bits in n & num, where & is the bitwise AND operator.

Return the number n.

 

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:

  • 1 <= 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 number exists inside the judge, and you can ask bitwise-style questions to learn about it. The goal is to reconstruct the exact value using the fewest queries by exploiting properties of bit manipulation rather than guessing numbers directly.

Approach 1: Naive Guessing (O(N) queries, O(1) space)

The most straightforward idea is to repeatedly guess numbers and check whether the judge confirms the answer. This effectively scans the entire search space until the correct value appears. While conceptually simple, the approach is impractical because the hidden number may lie in a large range. Each guess provides minimal information, so the number of required interactions grows linearly with the range size.

Approach 2: Bit-by-Bit Enumeration (O(B) queries, O(1) space)

A better strategy reconstructs the number one bit at a time. Instead of guessing whole numbers, send queries using a mask that isolates a single bit, typically 1 << i. The judge’s response reveals whether the hidden number contributes to that bit position. If the response indicates the bit is present, set that bit in your answer using a bitwise OR. Repeat this process for every bit position.

This works because each query reveals independent information about a single binary digit. After iterating through all bit positions, the combined bits form the hidden number. The algorithm relies on basic operations such as shifting (1 << i), masking, and combining bits with OR. These operations are fundamental to bit manipulation and commonly appear in interactive problems where each query must extract maximum information.

Recommended for interviews: The bit-by-bit enumeration approach is what interviewers expect. A brute-force guess demonstrates understanding of the problem space, but reconstructing the number using masks shows you know how to reason about binary representation and minimize queries. Interviewers typically look for the insight that each query can reveal one bit, reducing the total number of interactions to the number of bits in the integer.

Solution

We can enumerate the powers of 2, and then call the commonSetBits method. If the return value is greater than 0, it means that the corresponding bit in the binary representation of n is 1.

The time complexity is O(log n), where n \le 2^{30} in this problem. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive GuessingO(N) queriesO(1)Only for very small ranges or conceptual understanding
Bit-by-Bit EnumerationO(B) queriesO(1)Best approach when queries reveal bitwise information about the hidden number

Video Solution

3064. Guess the Number Using Bitwise Questions I (Leetcode Medium) • Programming Live with Larry • 155 views views

Frequently Asked Questions

Is Guess the Number Using Bitwise Questions I easy or hard?
The problem is rated Medium but conceptually straightforward once you recognize that each query can reveal one bit of the hidden number. Candidates familiar with bit masking and interactive patterns usually solve it quickly.
Guess the Number Using Bitwise Questions I Python/Java solution
The implementation loops through bit positions and sends a query using a single-bit mask. If the judge response indicates the bit exists, update the answer using ans |= (1 << i). The same logic works across Python, Java, C++, Go, and TypeScript because bitwise operations behave consistently across these languages.
How to solve Guess the Number Using Bitwise Questions I in O(B)?
Iterate through every bit position from 0 to the maximum possible bit. For each position, send a query with a mask containing only that bit (1 << i). If the response indicates the hidden number contributes to that bit, set the bit in the answer using bitwise OR. After processing all bits, the constructed value equals the hidden number.
What is the best approach for Guess the Number Using Bitwise Questions I?
Bit-by-bit enumeration using bit masks is the optimal strategy. Query the judge with a mask such as 1 << i to determine whether the hidden number contains that bit. Repeat for all bit positions and combine the discovered bits to reconstruct the final value. This minimizes the number of queries and leverages binary representation directly.
Is Guess the Number Using Bitwise Questions I asked at Google/Amazon/Meta?
Problems involving bit reconstruction and interactive queries appear frequently in interviews at companies like Google and Meta. While the exact problem ID may not be asked directly, the underlying concepts—bit masking, minimizing queries, and reasoning about binary representations—are common interview themes.
What data structure is used in Guess the Number Using Bitwise Questions I?
The solution mainly relies on bitwise operations rather than complex data structures. Integer variables and bit masks are used to probe and reconstruct each bit of the hidden number. Operations such as shift, AND, and OR form the core of the algorithm.
What is the time complexity of Guess the Number Using Bitwise Questions I?
The optimal solution runs in O(B) queries where B is the number of bits in the integer (typically up to 30 or 31 for standard constraints). Each query determines the value of one bit. Space complexity remains O(1) because only the reconstructed number and loop variables are stored.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary