Given a non-empty array of integers in which every element appears exactly twice except for one, return the element that appears once. Use O(n) time and O(1) extra space.
Before you code
A hash set solves it in O(n) time but O(n) space. The constant-space answer works on the bits directly: there is an operation that cancels a value when it is applied twice.
Hints
- XOR (
^) sets each bit of the result where the two inputs differ. Sox ^ xis 0 andx ^ 0isx. - XOR is commutative and associative, so the order of the elements doesn't matter.
- XOR every element together. Each pair cancels to 0, and what remains is the single number. Negative numbers work too, because XOR acts on the two's-complement bits.
Production & complexity notes
When solving Single number on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Bits, bytes and number representation to reinforce the underlying pattern.
What it practices
Treating integers as bit patterns, from Bits, bytes and number representation.