Problem Statement

Single Number III

You are given a list of whole numbers called nums. Almost every number shows up exactly twice. But two of them, call them a and b, show up only once. Your job is to find those two loners and return them. The trick we use is XOR. XOR is a way to combine two numbers bit by bit. Think of each bit as a light switch. XOR says: if the two bits are different, the result bit is on (1); if they are the same, the result bit is off (0). The magic property is that XOR cancels pairs: any number XORed with itself becomes 0, and any number XORed with 0 stays the same. So if we XOR every number in the list together, all the twins wipe each other out, and we are left with a XOR b, the two loners combined into one number.

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

Signals to notice

every element appears twice except twofind both unique elementsXOR then split

Brute force first

Hash map counting. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

XOR all elements — duplicates cancel, leaving a XOR b. Find any set bit in this XOR (it's a bit where a and b differ). Partition all numbers into two groups by this bit. XOR each group separately to get a and b. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `nums=[1,2,1,3,2,5]`

xor_all=0; XOR every element: 1^2^1^3^2^5 -> duplicates cancel -> xor_all=6 (binary 110) = 3 XOR 5
diff_bit = xor_all & (-xor_all) = 6 & -6 = 2 (binary 010): lowest bit where the two uniques differ
a=0; scan nums, XOR only those with (num & 2) != 0 -> qualifiers are 2,3,2
2: a=0^2=2 | 3: a=2^3=1 | 2: a=1^2=3 -> a=3 (the two 2's cancelled, leaving 3)
b = xor_all ^ a = 6 ^ 3 = 5
return [a, b] = [3, 5]

What must stay true

The XOR of all elements equals a XOR b (since all others cancel). Any set bit in this result differentiates a and b — partitioning by that bit separates them into different groups while keeping each group's duplicates paired. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

xor_all = 0
for num in nums: xor_all ^= num        # duplicates cancel -> a XOR b
diff_bit = xor_all & (-xor_all)         # isolate one differing bit
a = 0
for num in nums:
    if num & diff_bit: a ^= num         # group containing a; b = xor_all ^ a

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

Easy way to go wrong

Not understanding why the partition works — within each group, duplicates still cancel via XOR. The differentiating bit ensures a and b land in different groups. The fix is usually to return to the meaning of each move, not just the steps themselves.

Bit Manipulation Pattern