Problem Description

You need to find a hidden number n using a special API function.

The API provides a function commonSetBits(num) that takes an integer num as input and returns the count of bit positions where both n and num have a 1 in their binary representation. In other words, it counts the number of 1 bits in the result of n & num, where & is the bitwise AND operator.

For example, if n = 31 (binary: 11111) and you call commonSetBits(12) where 12 is binary 1100, the function would return 2 because:

• n & 12 = 11111 & 01100 = 01100
• This result has two 1 bits, so the function returns 2

Your task is to determine the value of n by making strategic calls to the commonSetBits function.

The solution works by checking each bit position individually. For each bit position i from 0 to 31, it calls commonSetBits(1 << i), which tests if bit i is set in n. The value 1 << i creates a number with only the i-th bit set to 1. If commonSetBits(1 << i) returns 1, it means that bit i is set in n. By testing all bit positions and combining the results, the complete value of n can be reconstructed using sum(1 << i for i in range(32) if commonSetBits(1 << i)).

The constraints ensure that n is between 1 and 2^30 - 1, and the num parameter passed to the API should be within 0 to 2^30 - 1 for reliable results.

Intuition

The key insight is that we need to reverse-engineer the hidden number n bit by bit. Since we can't directly access n, but we can probe it through the commonSetBits API, we need to think about what inputs to the API would give us useful information.

Consider what happens when we pass different values to commonSetBits:

• If we pass a random number, we get the count of overlapping 1 bits, but this doesn't tell us exactly which bits are set in n
• However, if we pass a number with only a single bit set, the API will return either 0 or 1, telling us definitively whether that specific bit is set in n

This leads to the strategy: test each bit position individually. For the i-th bit, we can create a test number with only that bit set using 1 << i. For example:

• 1 << 0 = 1 (binary: 0001) tests bit 0
• 1 << 1 = 2 (binary: 0010) tests bit 1
• 1 << 2 = 4 (binary: 0100) tests bit 2
• And so on...

When we call commonSetBits(1 << i):

• If bit i is set in n, then n & (1 << i) will have that single bit set, so the function returns 1
• If bit i is not set in n, then n & (1 << i) will be 0, so the function returns 0

By testing all 32 possible bit positions (since we're dealing with 32-bit integers), we can determine exactly which bits are set in n. Once we know all the set bits, we can reconstruct n by summing up the corresponding powers of 2: if bits at positions i, j, k are set, then n = 2^i + 2^j + 2^k.

This approach guarantees we find the exact value of n with just 32 API calls, one for each bit position.

Solution Approach

The implementation follows a straightforward bit manipulation strategy to reconstruct the hidden number n.

The algorithm iterates through all possible bit positions from 0 to 31 (covering the range of a 32-bit integer). For each bit position i:

1. Create a test mask: Generate a number with only the i-th bit set using the left shift operation 1 << i. This creates values like:

   • When i = 0: 1 << 0 = 1 (binary: 00...001)
   • When i = 1: 1 << 1 = 2 (binary: 00...010)
   • When i = 2: 1 << 2 = 4 (binary: 00...100)

2. Test the bit: Call commonSetBits(1 << i) to check if bit i is set in n. Since our test number has only one bit set:

   • If n has bit i set, the AND operation n & (1 << i) produces a non-zero result with exactly one bit set, so commonSetBits returns 1
   • If n doesn't have bit i set, the AND operation produces 0, so commonSetBits returns 0

3. Accumulate the result: If commonSetBits(1 << i) returns a non-zero value (which will be 1), we add 1 << i to our result. This effectively sets bit i in our reconstructed number.

The Python implementation uses a generator expression with sum() to elegantly combine these steps:

return sum(1 << i for i in range(32) if commonSetBits(1 << i))

This line:

• Iterates through bit positions 0 to 31
• For each position i, checks if commonSetBits(1 << i) is non-zero
• If true, includes 1 << i in the sum
• The sum of all these powers of 2 reconstructs the original number n

For example, if n = 31 (binary: 11111):

• commonSetBits(1) returns 1, so we add 1
• commonSetBits(2) returns 1, so we add 2
• commonSetBits(4) returns 1, so we add 4
• commonSetBits(8) returns 1, so we add 8
• commonSetBits(16) returns 1, so we add 16
• Sum: 1 + 2 + 4 + 8 + 16 = 31

The time complexity is O(32) = O(1) since we always make exactly 32 API calls, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through finding the hidden number n = 13 (binary: 1101).

We'll test each bit position from 0 to 31 by calling commonSetBits with powers of 2:

Bit position 0 (testing with 1):

• Test number: 1 << 0 = 1 (binary: 0001)
• n & 1 = 1101 & 0001 = 0001 (has 1 bit set)
• commonSetBits(1) returns 1 ✓
• Add 1 to our result

Bit position 1 (testing with 2):

• Test number: 1 << 1 = 2 (binary: 0010)
• n & 2 = 1101 & 0010 = 0000 (has 0 bits set)
• commonSetBits(2) returns 0 ✗
• Don't add anything

Bit position 2 (testing with 4):

• Test number: 1 << 2 = 4 (binary: 0100)
• n & 4 = 1101 & 0100 = 0100 (has 1 bit set)
• commonSetBits(4) returns 1 ✓
• Add 4 to our result

Bit position 3 (testing with 8):

• Test number: 1 << 3 = 8 (binary: 1000)
• n & 8 = 1101 & 1000 = 1000 (has 1 bit set)
• commonSetBits(8) returns 1 ✓
• Add 8 to our result

Bit positions 4-31:

• All return 0 since n = 13 has no bits set beyond position 3

Final reconstruction:

• Sum all the powers of 2 where we got a positive response
• Result = 1 + 4 + 8 = 13 ✓

We successfully recovered the hidden number by identifying that bits 0, 2, and 3 are set, which corresponds to 2^0 + 2^2 + 2^3 = 1 + 4 + 8 = 13.

Solution Implementation

Time and Space Complexity

The time complexity is O(1). The code iterates through a fixed range of 32 iterations (from 0 to 31), and in each iteration, it calls the commonSetBits API with a single bit set (powers of 2). Since the loop runs exactly 32 times regardless of input, and assuming commonSetBits runs in O(1) time, the overall time complexity is constant.

However, the reference answer states O(log n) where n ≤ 2^30. This suggests that the commonSetBits API itself has O(log n) complexity when processing the hidden number n. Since we make 32 calls to commonSetBits, and each call has complexity based on the hidden number being searched, the total time complexity would be O(32 * log n) = O(log n).

The space complexity is O(1). The algorithm uses only a constant amount of extra space for the loop variable i and temporary calculations. The generator expression is evaluated lazily and doesn't create an intermediate list, so no additional space proportional to the input is required.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Range Assumption

A common mistake is assuming the wrong range for bit positions. Developers might iterate through only 30 bits (0 to 29) based on the constraint that n is between 1 and 2^30 - 1, thinking they don't need to check bit position 30.

Wrong approach:

for bit_position in range(30):  # Missing potential bits!
    mask = 1 << bit_position
    if commonSetBits(mask):
        result += mask

Why it's wrong: Even though n is constrained to be less than 2^30, the value 2^30 - 1 requires 30 bits to represent (bits 0 through 29). The confusion often comes from mixing up "30 bits" with "bit position 30".

Correct approach: Always iterate through at least 30 bit positions (0 to 29) to cover all possible values up to 2^30 - 1. Using range(32) is safe and standard practice for 32-bit integers.

2. Using OR Operation Instead of Addition

Some developers might try to use the bitwise OR operator to combine bits instead of addition.

Potentially problematic approach:

result = 0
for bit_position in range(32):
    mask = 1 << bit_position
    if commonSetBits(mask):
        result |= mask  # Using OR instead of addition

Why it could be confusing: While this actually works correctly (since each bit position is unique and we're only setting each bit once), it's less intuitive than addition and might confuse code reviewers. The addition approach makes it clearer that we're summing powers of 2.

3. Misunderstanding the API Return Value

A critical mistake is assuming commonSetBits returns the actual bit value rather than the count.

Wrong interpretation:

result = 0
for bit_position in range(32):
    mask = 1 << bit_position
    bit_value = commonSetBits(mask)
    result += bit_value << bit_position  # Wrong! bit_value is already 0 or 1

Why it's wrong: The API returns the COUNT of common bits (0 or 1 in our case), not the bit pattern itself. When we query with a single-bit mask, the return value is either 0 (bit not set) or 1 (bit is set).

Correct approach: Use the return value as a boolean condition and add the mask itself to the result.

4. Inefficient Multiple API Calls for the Same Position

Some implementations might accidentally call the API multiple times for the same bit position.

Inefficient approach:

result = sum(1 << i for i in range(32) if commonSetBits(1 << i))
# Later in code, checking again unnecessarily
verification = all(commonSetBits(1 << i) for i in range(32) if result & (1 << i))

Why it's problematic: Each API call might have overhead in a real system. Making redundant calls doubles the number of operations without providing additional information.

Best practice: Store API results if you need them multiple times, or structure your code to make exactly one call per bit position.