Every element of nums appears twice except for one, which appears once. Find that single one, in linear time and using only constant extra space.
nums = [4,1,2,1,2]4nums = [2,2,1]1acc = 0 (XOR's "nothing")x: acc ^= x 🔄 flips the bits where x has a 1acc: pairs have cancelled, the single number is left ⭐"Different → 1, same → 0". Each bit column of acc is just the parity (odd/even count) of the 1s seen in that column. Paired numbers add an even count, so only the single number's bits stay odd.
Works for negative numbers too (the sign bit cancels the same way). A HashSet also works but costs O(n) space, and sorting costs O(n log n). Related: 137 (every other number appears 3×: count bits mod 3) and 260 (two singles: split them by one differing bit).
A hash map of counts works, but it uses O(n) extra space. Sorting and scanning pairs takes O(n log n).
Use the exclusive or operator, written as a caret. A number XOR itself is 0, and a number XOR 0 is the number itself. XOR is also order independent, so pairs can cancel no matter where they appear. XOR all the numbers together, and every pair cancels, leaving only the single one.
X XOR x is 0, and x XOR 0 is x. XOR everything, and pairs disappear.
Run the animation above on your own input, or watch the 1:31 video explanation of Single Number with a dry run and Java code.