Single Number - The Idea

The insight: XOR all the numbers together. Every number that appears twice will cancel itself out ($x \wedge x = 0$). What remains is the unique number.

For $[4, 1, 2, 1, 2]$: compute $4 \wedge 1 \wedge 2 \wedge 1 \wedge 2$. Since XOR is commutative, rearrange: $(1 \wedge 1) \wedge (2 \wedge 2) \wedge 4 = 0 \wedge 0 \wedge 4 = 4$.

This works because XOR has the self-canceling property and the identity element is 0.