Every number in the array appears twice, except for one. Find that single number, in linear time and constant extra space.
DSA Animator › DSA Revision › Bit Manipulation › Single Number
Remember: x XOR x is 0, and x XOR 0 is x. XOR everything, and pairs disappear. The video solves Single Number (LeetCode 136, Easy) with the XOR pattern from the Bit Manipulation topic, and you can replay every step in the interactive Single Number animation.
Every number in the array appears twice, except for one. Find that single number, in linear time and constant extra space.
For 4, 1, 2, 1, 2, the answer is 4.
A hash map of counts works, but it uses O of n extra space. Sorting and scanning pairs takes O of 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.
Start with 0. 0 XOR 4 is 4, which is 100 in binary. 4 XOR 1 is 5, and 5 XOR 2 is 7. 7 XOR 1 is 6, because the 1 bit cancels. 6 XOR 2 is 4, because the 2 bit cancels too. Only 4 remains, so the answer is 4.
In code, set result to 0. For each number, set result to result XOR the number. Return result, so it's O of n time and O of 1 space.
Remember: x XOR x is 0, and x XOR 0 is x. XOR everything, and pairs disappear.