Problem Statement

Single Number II

You are given a list of whole numbers. Every number shows up exactly three times, except for one number that shows up only once. Your job is to find that lonely number. There are two extra rules: you have to do it in one pass through the list (linear time), and you can only use a fixed, tiny amount of extra memory (constant space), so you cannot just count everything in a big table. The trick is to look at the numbers in binary, the 1s and 0s a computer actually stores. We count how many times each binary bit has appeared, but we only care about that count "mod 3", meaning we let it wrap back to zero every time it hits three. When a bit has shown up three times, it cancels out and disappears. Whatever bits are left belong to the number that appeared once.

mediumBit ManipulationBit ManipulationTime: O(n) · Space: O(1)

Signals to notice

every element appears 3 times except onefind the unique elementbit counting modulo 3

Brute force first

Hash map to count frequencies. Works but uses extra memory. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Count bits at each of 32 positions modulo 3. The unique number's bits are the remainders. Or use two variables (ones, twos) to track bit states. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `nums=[2,2,3,2] (2=10b, 3=11b)`

start: ones=0, twos=0
num=2: twos|=0&2=0; ones^=2->10; threes=0 -> ones=2(10), twos=0
num=2: twos|=2&2=2; ones^=2->0; threes=0 -> ones=0, twos=2(10)
num=3: twos|=0&3 stays 2; ones^=3->11; threes=11&10=10 -> clear bit -> ones=1(01), twos=0
num=2: twos|=1&2=0; ones^=2 -> 01^10=11; threes=11&0=0 -> ones=3(11), twos=0
loop done -> return ones=3

What must stay true

If every number appears 3 times, each bit position has a total count divisible by 3. The unique number's contribution is the remainder when dividing each bit position's count by 3. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

ones, twos = 0, 0
for num in nums:
    twos |= ones & num      # bit reached 2nd time
    ones ^= num             # toggle bit's 1st-time state
    threes = ones & twos    # bit hit 3 times -> clear it
    ones &= ~threes; twos &= ~threes
return ones                 # bits seen exactly once

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying to use XOR like Single Number I — XOR only cancels pairs (appearing twice). For triples, you need modulo-3 bit counting. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Bit Manipulation Pattern