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.

The key of the solution is to split the input into two groups, each single number belongs to different groups. This is done by nums[i] ^ lowestBit.

But what is lowestBit?

Assume a, b represents the two single numbers in the input vector.

Well, if we xor the whole input vector, we got the variable xOR which is the xor result of a and b.

Then we find the lowest non-zero bit of xOR. We know that a and b must be different at this bit.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // assume nums.size() >= 2
        int xOR = 0;
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            xOR = xOR ^ nums[i];
        }
        //find the first non-zero bit
        int lowestBit = 1;
        for(int i = 0; i < 32; i++){
            if(1 & xOR){
                break;
            }
            else{
                xOR = xOR >> 1;
                lowestBit = lowestBit << 1;
            }
        }
        int a = 0;
        int b = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] & lowestBit){
                a = a ^ nums[i];
            }else{
                b = b ^ nums[i];
            }
        }
        ans.push_back(a);
        ans.push_back(b);
        return ans;
    }
};