// https://leetcode.com/problems/single-number-iii/

// Given an integer array 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. You can return the answer in any order.

// You must write an algorithm that runs in linear runtime complexity and uses only
// constant extra space.

////////////////////////////////////////////////////////////////////////////////

// XOR all nums -> aXORb = a XOR b -> need to seperate a and b
// get lowbit(aXORb) to seperate data (guarantee to seperate a and b)
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long aXORb = 0;
        for (int num : nums) aXORb ^= num;
        int lowbit = aXORb & -aXORb;
        
        vector<int> ans(2, 0);
        for (int num : nums) {
            if (num & lowbit) ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }
};
