Single Number

Problem

You are given an array of integers in which every value appears exactly twice except for one value, which appears exactly once. Find that value. Your solution must run in linear time and must not allocate memory proportional to the input size.

• The array holds at most 30,000 elements.
• Values fit comfortably in a 32-bit signed range.
• Exactly one element appears once; every other element appears exactly twice.

Examples

• nums = [5, 5, 9] → 9.
• nums = [8, 3, 6, 3, 6] → 8; the pairs 3,3 and 6,6 cancel out.
• nums = [-12] → -12; a single element is trivially the answer, and negatives are allowed.

Hints

1. A hash map of counts solves it easily, but it uses O(n) space. What operation "cancels out" two equal numbers?
2. Look for an operation that is commutative and associative, so order does not matter, and where x op x is the identity.
3. XOR all the numbers together: pairs cancel to 0, and 0 ^ x = x.