Single Number II (LeetCode 137)

The problem

You get an array where every value appears exactly three times, except one value that appears once. Return that value in O(n) time and O(1) extra space.

Input:  [2, 2, 3, 2]
Output: 3

2 appears three times; 3 appears once.

How to think about it

Start with brute force. A hash map of counts gives O(n) time but O(n) space. Plain XOR, the trick from Single Number, does not work: three copies XOR to the number itself, not to 0.

The key insight: count each bit modulo 3. Look at one bit position. Each triple adds 0 or 3 to the count of 1s there; the single number adds 0 or 1. So count mod 3 at that position is exactly the single number’s bit. You could keep 32 counters, one per bit. That is O(32·n), fine, but there is a neater way.

Two masks act as a per-bit counter. A count mod 3 has three states (0, 1, 2), which fits in two bits. Keep two integers: ones holds the bits whose count is 1, and twos holds the bits whose count is 2. For each x:

• ones = (ones ^ x) & ~twos: toggle x’s bits into ones, but not for bits already counted twice.
• twos = (twos ^ x) & ~ones: toggle into twos, but not for bits that just landed in ones.

A bit seen a third time is cleared from both, which resets that bit’s count to 0. At the end, ones holds exactly the bits seen once mod 3: the answer.

Which pattern is this? Bit manipulation, per-bit counting. The tell is “appears k times except one”. The same idea works for any k.

Approach

1. Start with ones = twos = 0.
2. For each x, update ones = (ones ^ x) & ~twos, then twos = (twos ^ x) & ~ones. The order matters: twos uses the new ones.
3. Return ones.

Solution

def single_number_ii(nums):
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos   # bits seen once (mod 3)
        twos = (twos ^ x) & ~ones   # bits seen twice (mod 3)
    return ones
# single_number_ii([2,2,3,2]) -> 3

Dry run

On [2, 2, 3, 2], with the masks in two-bit binary:

ones is 11, which is 3.

Complexity

• Time: O(n). Constant work per element.
• Space: O(1). Two integers.

Edge cases and pitfalls

• Single element ([5]) returns 5.
• Negative numbers work in Python because ~ and & act on two’s-complement bits: [-2,-2,1,1,4,1,4,4,-4,-2] returns -4. In the 32-counter version you must convert bit 31 back to a sign yourself.
• Updating twos with the old ones breaks the state machine. Update ones first.
• Plain XOR returns the XOR of everything, which is wrong when numbers appear three times.

Related problems

• Single Number (LeetCode 136): the pairs version, where plain XOR works.
• Single Number III (LeetCode 260): two singles among pairs.
• Number of 1 Bits (LeetCode 191): more practice thinking one bit position at a time.