Maintained by Vikas Dulgunde, software engineer
You receive an array of integers in which all but one value show up exactly twice. The remaining value appears a single time. Your job is to identify and return that lone value.
The array is never empty, and the duplicated values can sit anywhere relative to one another, in any order. There is always exactly one value without a partner.
The interesting part is the resource budget. A counting map would work but costs extra memory proportional to the input. The expectation here is a pass that runs in linear time while holding only a fixed amount of extra state, regardless of how large the array grows.
Two appears twice and cancels out, so 1 is the only value left standing alone.
The two 1s pair off and the two 2s pair off, leaving 4 as the unmatched value even though it sits at the front.
Negative values pair just like positive ones, so the two -1s cancel and 9 remains.
Visible test cases
A hash map that counts how many times each value appears would solve it, but think about whether you can avoid storing all those counts.
Pairs of equal values should somehow neutralize each other, so the operation you fold over the array needs that cancelling behavior.
XOR has two useful properties: any value XOR itself is 0, and any value XOR 0 is unchanged. Fold XOR across the whole array and the pairs vanish.
Tally how often each value occurs, then return the one with a count of one.
XOR is associative and commutative, a value XOR itself is 0, and a value XOR 0 is itself, so XORing every element together cancels all the pairs and leaves only the lone value.