Problem Description

You need to find a hidden number n that is between 0 and 2^30 - 1 (inclusive).

You're given an API function commonBits(num) that you can use to help find this number. However, there's a twist - each time you call this function, the value of n changes! Your goal is to find the initial value of n.

Here's how commonBits(num) works:

1. It counts how many bit positions have the same value in both n and num (looking at their binary representations)
2. It then updates n by performing XOR operation: n = n XOR num
3. It returns the count from step 1

For example, if n = 5 (binary: 101) and you call commonBits(3) where 3 is binary 011:

• Common bits: positions where both have same value = 1 (only the middle bit)
• After the call: n becomes 5 XOR 3 = 6 (binary: 110)
• Returns: 1

The challenge is that since n keeps changing with each API call, you need a clever strategy to determine what n was originally. The solution uses the fact that calling commonBits with the same argument twice in a row has a special property - the second call undoes the XOR effect of the first call, returning n to its state before both calls. By strategically using powers of 2 (1 << i), which have only a single bit set, you can probe each bit position of the original n individually.

Intuition

Let's think about what happens when we call commonBits with a power of 2, like 1 << i, which has only the i-th bit set to 1.

When we XOR n with 1 << i, only the i-th bit of n gets flipped - all other bits remain unchanged. This is because XOR with 0 keeps a bit the same, and XOR with 1 flips it.

Now here's the key insight: if we call commonBits(1 << i) twice in a row:

• First call: flips the i-th bit of n and returns a count
• Second call: flips the i-th bit again, returning it to its original state, and returns a different count

The crucial observation is that these two counts tell us about the original i-th bit of n:

• If the i-th bit was originally 1, then the first call would see a match at position i (both have 1), giving a higher count
• After flipping, the i-th bit becomes 0, so the second call sees a mismatch at position i (one has 0, other has 1), giving a lower count
• Therefore: count1 > count2 means the i-th bit was originally 1

Conversely:

• If the i-th bit was originally 0, the first call sees a mismatch (lower count)
• After flipping to 1, the second call sees a match (higher count)
• Therefore: count1 < count2 means the i-th bit was originally 0

By testing each bit position from 0 to 29 (or 31 in the code) independently using this double-call technique, we can reconstruct the entire original value of n bit by bit. The beauty of this approach is that after two calls with the same value, n returns to its current state (due to XOR being self-inverse), so we can test each bit without permanently affecting the others.

Solution Approach

The implementation uses bit manipulation to reconstruct the original value of n bit by bit.

We initialize n = 0 to store our result. Then, for each bit position i from 0 to 31:

1. Create a test number: We use 1 << i to create a number with only the i-th bit set to 1. For example, 1 << 2 gives us 4 (binary: 100).

2. Call the API twice:

   count1 = commonBits(1 << i)
   count2 = commonBits(1 << i)

   The first call flips the i-th bit of the hidden n and returns the count of common bits before the flip. The second call flips it back and returns the count after the first flip.

3. Determine the original bit value:

   • If count1 > count2, the i-th bit of the original n was 1
   • If count1 < count2, the i-th bit of the original n was 0
   • If count1 == count2, the i-th bit doesn't affect the count (it was 0)

4. Set the bit in our result: If we determined the i-th bit was 1, we set it in our result using the OR operation:

   if count1 > count2:
       n |= 1 << i

   The expression n |= 1 << i sets the i-th bit of n to 1 while keeping all other bits unchanged.

5. Return the reconstructed number: After checking all 32 bits (though only 30 are relevant per the problem constraints), we have successfully reconstructed the original value of n.

The key pattern here is using XOR's self-inverse property: (n XOR x) XOR x = n. By calling the function twice with the same argument, we effectively probe each bit's original value without permanently affecting the hidden number's state for subsequent bit tests.

Example Walkthrough

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

Initial state: The hidden number is n = 5 (binary: 101)

Step 1: Test bit position 0 (rightmost bit)

• Call commonBits(1 << 0) which is commonBits(1) where 1 is binary 001
• Before XOR: n = 101, num = 001
  • Common bits: positions 1 and 2 match (both have 0), position 0 differs → count1 = 2
• After XOR: n = 101 XOR 001 = 100 (which is 4)
• Call commonBits(1 << 0) again with n = 100
  • Before XOR: n = 100, num = 001
  • Common bits: only position 1 matches → count2 = 1
• After XOR: n = 100 XOR 001 = 101 (back to 5)
• Since count1 (2) > count2 (1), bit 0 was originally 1
• Set bit 0 in result: result = 0 | 1 = 1

Step 2: Test bit position 1

• Call commonBits(1 << 1) which is commonBits(2) where 2 is binary 010
• Before XOR: n = 101, num = 010
  • Common bits: positions 0 and 2 match → count1 = 2
• After XOR: n = 101 XOR 010 = 111 (which is 7)
• Call commonBits(1 << 1) again with n = 111
  • Before XOR: n = 111, num = 010
  • Common bits: all positions match → count2 = 3
• After XOR: n = 111 XOR 010 = 101 (back to 5)
• Since count1 (2) < count2 (3), bit 1 was originally 0
• Result remains: result = 1

Step 3: Test bit position 2

• Call commonBits(1 << 2) which is commonBits(4) where 4 is binary 100
• Before XOR: n = 101, num = 100
  • Common bits: all positions match → count1 = 3
• After XOR: n = 101 XOR 100 = 001 (which is 1)
• Call commonBits(1 << 2) again with n = 001
  • Before XOR: n = 001, num = 100
  • Common bits: only position 1 matches → count2 = 1
• After XOR: n = 001 XOR 100 = 101 (back to 5)
• Since count1 (3) > count2 (1), bit 2 was originally 1
• Set bit 2 in result: result = 1 | 4 = 5

Final result: We've reconstructed the original value as 5 (binary: 101)

The pattern is clear: when count1 > count2, the tested bit was originally 1; when count1 < count2, it was originally 0. After testing each bit position twice, the hidden number returns to its current state, allowing us to test the next bit independently.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n) where n represents the range of possible values (in this case, a 32-bit integer). The algorithm iterates through 32 bits (constant iterations), and for each bit position i, it calls the commonBits API twice. Since we're dealing with a fixed 32-bit integer representation, this can also be considered O(1) in terms of constant operations. However, more precisely, it's O(log n) because the number of bits needed to represent a number n is log₂(n).

The space complexity is O(1) because the algorithm only uses a constant amount of extra space. The variable n is used to store the result, and the loop variable i is used for iteration. No additional data structures that grow with input size are utilized.

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

Common Pitfalls

Pitfall 1: Incorrect Baseline Comparison

The code shown uses commonBits(0) as a baseline comparison, but this is problematic because:

• Calling commonBits(0) modifies the hidden number (XORing with 0 doesn't change it, but we're still "using up" a call)
• The comparison between count_with_bit and count_without_bit doesn't actually tell us about the original bit value
• The hidden number's state changes between the two calls, making the comparison meaningless

Solution: Use the double-call pattern with the same power of 2:

class Solution:
    def findNumber(self) -> int:
        result = 0
      
        for bit_position in range(30):  # Only need 30 bits per problem constraints
            # Call twice with the same value
            count1 = commonBits(1 << bit_position)
            count2 = commonBits(1 << bit_position)
          
            # First call tells us about original state, second call restores it
            if count1 > count2:
                result |= (1 << bit_position)
      
        return result

Pitfall 2: Misunderstanding the Count Comparison Logic

A common mistake is thinking that if count1 == count2, the bit must be 0. Actually:

• When count1 > count2: The i-th bit was originally 0 (flipping it to 1 increased matches)
• When count1 < count2: The i-th bit was originally 1 (flipping it to 0 decreased matches)

The logic in the problem description appears reversed!

Solution: Correct the bit-setting logic:

if count1 < count2:  # Original bit was 1
    result |= (1 << bit_position)

Pitfall 3: Not Preserving Hidden Number State

Each call to commonBits modifies the hidden number. If you don't use the double-call pattern correctly, subsequent bit checks will be working with a corrupted version of the hidden number.

Solution: Always call commonBits twice with the same argument to ensure the hidden number returns to its pre-call state before checking the next bit position. This preserves the integrity of the hidden number for subsequent bit checks.