Exactly two numbers appear once, and every other number appears twice. Find the two single numbers, in linear time and constant space.
DSA Animator › DSA Revision › Bit Manipulation › Single Number III
Remember: one differing bit separates the two singles. x AND minus x isolates the lowest set bit. The video solves Single Number III (LeetCode 260, Medium) with the XOR + Split by Bit pattern from the Bit Manipulation topic, and you can replay every step in the interactive Single Number III animation.
Exactly two numbers appear once, and every other number appears twice. Find the two single numbers, in linear time and constant space.
For 1, 2, 1, 3, 2, 5, the answer is 3 and 5.
A hash set works, but uses extra space. Plain XOR of everything gives 3 XOR 5, not the two numbers themselves.
XOR everything, and the pairs cancel, leaving x equal to a XOR b. Because a and b are different, x has at least one 1 bit, where a and b differ. Take the lowest set bit of x, using x AND minus x. Split the numbers into two groups by that bit, so a and b land in different groups. Pairs stay together, so XOR each group to get a and b.
XOR of everything is 6, which is 110. The lowest set bit of 6 is 2, which is 010. Numbers with that bit are 2, 3 and 2, and their XOR is 3. Numbers without it are 1, 1 and 5, and their XOR is 5. So the answer is 3 and 5.
In code, XOR all numbers into x. Compute low as x AND minus x. XOR numbers with that bit into one result, and the others into a second result. Return both, so it's O of n time and O of 1 space.
Remember: one differing bit separates the two singles. x AND minus x isolates the lowest set bit.