Clinic #32: Single Number

The five moves a processor can make on a number’s row of switches. This clinic uses one of them, XOR, the move that flips a switch only where two rows disagree, and shows why it is the whole answer to one of the most asked easy problems.

Before you start. A computer stores every whole number as a row of ones and zeros, a row of switches read in twos instead of tens, so 101 is one four and one one, five. Bit Manipulation (thinking in bits) shows that row and the moves on it; this clinic needs only the row itself, and builds the one move it uses from scratch.

The idea in 30 seconds

Single Number: every value appears twice except one; find it with work that grows in step with the list (linear time) and scratch memory that never grows (constant extra space).
Hunting for each value’s twin works but costs O(n²): double the list, four times the work.
Remembering what you have seen is linear time but its memory grows with the list, which breaks the space rule.
XOR compares two numbers’ binary digits and gives 1 wherever they disagree; a number XOR itself is 0, XOR 0 is itself, and order never matters.
So XOR-ing the whole list cancels every pair and leaves the single; the running result is the XOR of everything still unpaired.
“Appears twice except one” plus “constant space” in a problem is the sign that names XOR.

Read the story · Skip to the numbers