LeetCode Q260: Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

We need to use XOR to solve this problem. Two passes are needed.

In the first pass, we use XOR to cancel out all paired numbers and get the bit difference of two single numbers. (Results of XOR on entire array will be bit difference of two distinct numbers.).

In the second pass, we can divide all numbers to two groups. We look at the any bit set to 1 in result of the first pass. We use that bit to separate numbers to the groups. Because the result of pass one indicate the bit difference of two numbers, so two numbers will be separate to two groups separately. Then we can run XOR to group to get two numbers.