Introduction

In Single Number II, every integer appears three times except one value that appears once. The challenge is to find that unique value in linear time and constant extra space. A counting hash map works logically, but it violates the space goal. The intended solution is bit manipulation.

The Core Observation

Look at one bit position at a time. If every repeated number appears exactly three times, then the total number of 1 bits contributed by those repeated numbers is a multiple of 3.

Only the unique number leaves a remainder.

So for each bit position:

• count how many numbers have that bit set
• take the count modulo 3
• rebuild the answer from the remainders

Straightforward 32-Bit Solution

This version is easy to explain and works well in interviews.

1
2def single_number(nums):
3    result = 0
4
5    for bit in range(32):
6        count = 0
7        for num in nums:
8            if (num >> bit) & 1:
9                count += 1
10
11        if count % 3:
12            result |= (1 << bit)
13
14    # convert from unsigned 32-bit to signed integer if needed
15    if result >= 2**31:
16        result -= 2**32
17
18    return result
19
20
21print(single_number([2, 2, 3, 2]))
22print(single_number([0, 1, 0, 1, 0, 1, 99]))

This runs in O(32n), which is still O(n) because 32 is constant.

Why the Modulo Step Works

Suppose bit 5 is set in numbers that appear three times. Their total contribution to that bit count is 3, 6, 9, and so on. All of those disappear under modulo 3.

If the unique number also has bit 5 set, the final remainder becomes 1, so we set that bit in the result.

This is the cleanest proof of correctness.

The Constant-State Bitmask Trick

There is also a more compact solution using two bitmasks, usually called ones and twos. These masks simulate counting each bit modulo 3 without explicitly looping over 32 bit positions.

1
2def single_number(nums):
3    ones = 0
4    twos = 0
5
6    for num in nums:
7        ones = (ones ^ num) & ~twos
8        twos = (twos ^ num) & ~ones
9
10    return ones
11
12
13print(single_number([2, 2, 3, 2]))
14print(single_number([0, 1, 0, 1, 0, 1, 99]))

This solution is elegant, but it is harder to derive under pressure. In interviews, the 32-bit counting version is often easier to justify clearly.

Understanding ones and twos

For each bit position, ones tracks bits seen once modulo 3, and twos tracks bits seen twice modulo 3.

When a bit is seen for the third time, it is cleared from both masks. By the end, only bits belonging to the unique number remain in ones.

This is effectively a tiny state machine implemented with bitwise operators.

Handling Negative Numbers

In languages with fixed-width integers such as Java or C++, signed behavior follows the machine word size naturally. In Python, integers are unbounded, so the 32-bit reconstruction version usually needs the signed conversion step at the end.

That is why the code above subtracts 2**32 when the highest sign bit is set.

Interview Tradeoffs

If the interviewer emphasizes readability and proof, the per-bit counting solution is strong.

If the interviewer pushes for the most elegant constant-space formulation, the ones and twos method is usually the intended advanced answer.

Both satisfy linear time and constant extra space.

Common Pitfalls

A common mistake is using a hash map even after the problem explicitly asks for constant extra space.

Another mistake is forgetting negative-number handling in Python when reconstructing the result from 32 bits.

Developers also sometimes memorize the ones and twos formula without understanding it, which makes it hard to explain or adapt under interview pressure.

Summary

• Count set bits modulo 3 to isolate the unique number.
• A 32-bit counting loop gives a clear O(n) and O(1) solution.
• The ones and twos bitmask technique is a more compact state-machine version.
• Watch for signed-integer behavior, especially in Python.
• The key idea is that repeated values vanish under modulo 3 bit counting.