Maintained by Vikas Dulgunde, software engineer
You receive a non-empty list of integers. The list is built so that each number is paired with an identical copy somewhere else in the list, with one single exception: exactly one number has no partner.
Your job is to find and return that unpaired number. The array is not sorted, the values can be negative or zero, and the lone number may sit anywhere in the list.
The interesting constraint is efficiency. A correct answer is easy, but the version interviewers look for runs in one pass over the array and uses only a fixed amount of extra memory regardless of input size.
The two 2s cancel as a pair, so 1 is the value left without a match.
The pair of 1s and the pair of 2s each cancel out, leaving 4 as the only unpaired number.
Negative values behave the same way: the two -1s pair off and -2 is the single number.
Visible test cases
A pair of equal numbers contributes nothing if you can find an operation where combining a value with itself produces a neutral result.
Bitwise XOR has two properties that matter here: x XOR x is 0, and x XOR 0 is x. Order does not matter either.
Fold the whole array together with XOR starting from 0. Everything that appears twice cancels to 0, so only the lone value survives.
Count how many times each value occurs, then return the one with an odd count.
XOR cancels equal pairs to zero, so XOR-ing every element together leaves only the unpaired one.