XOR cancels pairs

49 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

In [4, 1, 2, 1, 2] every number appears twice except one. Which one? By hand you would tick off pairs: the two 1s, the two 2s, leaving 4. That is easy with five numbers. With a million numbers you would need to sort them first (slow) or keep a tally of how many times each number has appeared, which needs memory the size of the input. The problem asks for one pass and no extra memory, which the tally cannot do.

Build the structure, one piece at a time

The tool is a single operation on binary numbers, XOR, written ⊕. Write both numbers in binary and compare bit by bit: the result has a 1 where the two bits differ and a 0 where they are the same. For example, 5 ⊕ 3: 101 ⊕ 011 = 110 = 6.

Three facts about ⊕ are all that is needed:

• a ⊕ a = 0, because every bit is the same as itself.
• a ⊕ 0 = a, because XOR with a zero bit leaves a bit unchanged.
• The order does not matter: a ⊕ b = b ⊕ a, and (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c), since each bit position is handled independently and for one bit XOR is just addition without carry.

So the structure is one number, an accumulator starting at 0, and the procedure is to XOR every element into it:

The accumulator ends at 4, the single number. Watch the second 1 arrive: it flips the lowest bit back off, undoing the first 1. The pairs cancel no matter how far apart they are.

Why it is correct

Because order does not matter, the final accumulator equals the XOR of all elements in any order you like. Reorder them so the pairs sit together: (1 ⊕ 1) ⊕ (2 ⊕ 2) ⊕ 4. Each pair is 0 by the first fact, and 0 ⊕ 0 ⊕ 4 = 4 by the second. In general, every number that appears an even number of times cancels completely, and what remains is the XOR of the numbers that appear an odd number of times. With exactly one such number, the accumulator is that number.

⊕ over all elements = ⊕ over elements with odd count, since a ⊕ a = 0

Why it is fast

One XOR per element: O(n) time, and the memory is a single integer, O(1). Sorting is O(n log n), and a tally is O(n) time but O(n) memory. XOR is also a single machine instruction, so the pass is as fast as reading the array.

How to recognise it in an interview

Cues: "every element appears twice except one", "find the missing number", "find the difference between two strings", or any setting where things come in pairs that should cancel. Say: XOR of a pair is zero, so XOR everything and the unpaired element survives. Single Number is the example. Missing Number XORs 0..n together with the array; every present number appears twice and cancels, leaving the missing one. Single Number III has two unpaired numbers: XOR everything to get a ⊕ b, pick any bit where they differ, and XOR the two groups separately.

02The idea in one line

a ⊕ a = 0, so pairs vanish and the lone element survives.

Reach for it when: Single number, missing number, find the difference, single number III.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Single Number on [4,1,2,1,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. XOR everything into one accumulator, starting at 0
2. Bring in 4 = 0100
3. acc ⊕ x = 4: a bit stays 1 only where exactly one side has it
4. Bring in 1 = 0001
5. acc ⊕ x = 5: a bit stays 1 only where exactly one side has it
6. Bring in 2 = 0010
7. acc ⊕ x = 7: a bit stays 1 only where exactly one side has it
8. Bring in 1 = 0001
9. acc ⊕ x = 6: a bit stays 1 only where exactly one side has it
10. Bring in 2 = 0010
11. acc ⊕ x = 4: a bit stays 1 only where exactly one side has it
12. The pairs 1⊕1 and 2⊕2 vanished; what survives is 4
13. One pass, one integer of memory: O(n) time, O(1) space

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Bit Manipulation: Bit tricks (n & (n−1), masks), Enumerate subsets by mask.