Single Number - The Idea

XOR has a special property: $A \oplus A = 0$ and $A \oplus 0 = A$. If you XOR all numbers together, pairs cancel out (become 0), leaving only the single number.

Example: $2 \oplus 2 \oplus 1 = 0 \oplus 1 = 1$. Example: $4 \oplus 1 \oplus 2 \oplus 1 \oplus 2 = 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 = 4$.

XOR is commutative and associative, so order doesn't matter. You can XOR all elements in one pass, using $O(1)$ space.