LeetCode 3064 - Guess the Number Using Bitwise Questions I

LeetCode Problem 3064

Difficulty: 🟡 Medium
Topics: Bit Manipulation, Interactive

Solution

Problem Understanding

The problem presents an interactive scenario where there is a hidden number n in the range [1, 2^30 - 1]. We are provided with an API commonSetBits(num) which returns the count of bits that are set in both n and num when performing a bitwise AND. In other words, commonSetBits(num) computes the number of positions where both n and num have a 1 bit. Our task is to determine the exact value of n using this API.

The input is not given explicitly; instead, the algorithm interacts with the API. The expected output is the integer n. The constraints limit n and num to 30-bit integers, which informs us that the maximum number of bits we need to check is 30. Edge cases involve small numbers (like 1) or numbers where only the highest bit is set, as these might challenge naive bitwise deductions.

Approaches

Brute Force

A brute-force approach would iterate through every possible integer from 1 to 2^30 - 1 and use commonSetBits to check if all bits match the response. If a match is found for all bits, that number is n. This is correct because it exhaustively tests every candidate, but it is infeasible for 2^30 numbers, as it would require up to roughly 1 billion API calls, which is too slow.

Optimal Approach

The key observation is that commonSetBits allows us to test each bit individually. We can construct a number res bit by bit. For each bit position i from 0 to 29, we query commonSetBits(1 << i). If the API returns 1, it means the bit i in n is set. If it returns 0, the bit is not set. By systematically testing all 30 bits, we can reconstruct n in exactly 30 API calls.

This approach leverages the fact that commonSetBits(1 << i) isolates the contribution of a single bit, which gives a direct yes/no answer for that bit.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^30)	O(1)	Test every number against the API
Optimal	O(30)	O(1)	Test each bit individually using 1 << i

Algorithm Walkthrough

1. Initialize a variable res = 0. This will store the reconstructed number.
2. Iterate over all bit positions i from 0 to 29.
3. For each bit i, query commonSetBits(1 << i). This isolates the i-th bit of n.
4. If the API returns 1, set bit i in res using res |= (1 << i).
5. If the API returns 0, leave bit i unset.
6. After processing all bits, res will contain the number n.
7. Return res.

Why it works: Each query isolates a single bit. Because commonSetBits counts the number of set bits in common, querying 1 << i gives a response of 1 if and only if that bit is set in n. This guarantees that after 30 queries, we reconstruct all bits of n.

Python Solution

# Definition of commonSetBits API.
# def commonSetBits(num: int) -> int:

class Solution:
    def findNumber(self) -> int:
        res = 0
        for i in range(30):
            if commonSetBits(1 << i) == 1:
                res |= (1 << i)
        return res

The Python implementation follows the algorithm exactly. We iterate over each bit position from 0 to 29 and query the API with 1 << i. If the API returns 1, we set that bit in the result. Otherwise, we leave it unset. Finally, the constructed number res is returned.

Go Solution

/** 
 * Definition of commonSetBits API.
 * func commonSetBits(num int) int;
 */

func findNumber() int {
    res := 0
    for i := 0; i < 30; i++ {
        if commonSetBits(1 << i) == 1 {
            res |= (1 << i)
        }
    }
    return res
}

The Go implementation mirrors the Python version. We initialize res as 0, iterate through bits 0 to 29, check if the bit is set using the API, and update res accordingly. The main difference in Go is syntax, but the logic and number handling are identical.

Worked Examples

Example 1: n = 31

Bit i	Query 1<<i	commonSetBits Response	Action on res
0	1	1	set bit 0
1	2	1	set bit 1
2	4	1	set bit 2
3	8	1	set bit 3
4	16	1	set bit 4
5+	32, 64, ...	0	leave unset

Resulting res = 11111 binary = 31 decimal.

Example 2: n = 33

Bit i	Query 1<<i	commonSetBits Response	Action on res
0	1	1	set bit 0
1	2	0	leave unset
2	4	0	leave unset
3	8	0	leave unset
4	16	0	leave unset
5	32	1	set bit 5

Resulting res = 100001 binary = 33 decimal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(30) = O(1)	We make exactly 30 API calls, independent of n.
Space	O(1)	We store only the result integer.

The time complexity is effectively constant because the number of bits is bounded at 30. Space complexity is minimal, using only one integer to accumulate the result.

Test Cases

# Provided examples
assert Solution().findNumber() == 31  # n = 31
assert Solution().findNumber() == 33  # n = 33

# Boundary tests
assert Solution().findNumber() == 1          # smallest possible n
assert Solution().findNumber() == (1 << 30) - 1  # largest possible n

# Random bit patterns
assert Solution().findNumber() == 0b101010   # alternating bits
assert Solution().findNumber() == 0b100000   # single high bit
assert Solution().findNumber() == 0b11       # small number with two bits

Test	Why
n = 31	Checks multiple lower bits set
n = 33	Checks combination of low and high bits
n = 1	Edge case: smallest number
n = 2^30 - 1	Edge case: largest number
n = 0b101010	Random pattern with alternating bits
n = 0b100000	Single high bit set
n = 0b11	Small number with two bits set

Edge Cases

One important edge case is when n = 1, which tests the algorithm's handling of the smallest number. Only bit 0 should be set, and all other queries must correctly return 0, ensuring no higher bits are erroneously set.

Another edge case is n = 2^30 - 1, which tests the algorithm on the maximum possible 30-bit number. Every bit from 0 to 29 is set, so all API calls should return 1. This ensures that the code can handle numbers with many bits set without overflow or miscalculations.

A third edge case is a number with only the highest bit set, n = 1 << 29. This tests whether the implementation correctly handles a high bit without mistakenly affecting lower bits. The algorithm correctly queries each bit independently, so it accurately reconstructs n in this case as well.