In the list nums, every value appears exactly twice, except one value that appears only once.
Return that value.
Aim for a single pass that uses only a constant amount of extra memory.
Example 1
- Input
- nums = [5, 3, 5]
- Output
- 3
Example 2
- Input
- nums = [8, -2, 7, 8, 7]
- Output
- -2
Constraints
numsholds 1 to 29999 numbers.- −10⁹ ≤
nums[i]≤ 10⁹ - Every value appears twice, except exactly one that appears once.
Show the pattern
Bit manipulation
Every value comes in a pair except one, and XOR cancels equal values (`x ^ x = 0`) in any order, so XOR-ing everything together leaves the odd one out, with no extra memory.
Show the approach
XOR (^) compares numbers bit by bit: a bit of the result is 1 when exactly one of the two bits
is 1. So x ^ x = 0, x ^ 0 = x, and XOR doesn't care about order or grouping.
XOR all the numbers together. Rearranged, every pair becomes x ^ x = 0, and the zeros vanish,
leaving only the value that appears once. Negative numbers work too, since XOR acts on their
two's-complement bits.
Time: O(n) · Space: O(1)