260. Single Number III

1. Description

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.

2. Example

Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.

Example 2:
Input: nums = [-1,0]
Output: [-1,0]

Example 3:
Input: nums = [0,1]
Output: [1,0]

3. Constraints

• 2 <= nums.length <= 3 * $10^4$
• $-2^{31}$ <= nums[i] <= $2^{31}$ - 1
• Each integer in nums will appear twice, only two integers will appear once.

4. Solutions

Bit Manipulation

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    vector<int> singleNumber(const vector<int> &nums) {
        long single_number_xor = 0;
        for (auto num : nums) {
            single_number_xor ^= num;
        }

        int right_digit_diff = single_number_xor - (single_number_xor & (single_number_xor - 1));
        // find a number with single digit that one candidate has and another doesn't
        // here we get the most right digit one, but any one is OK
        int single_num1 = 0, single_num2 = 0;
        for (auto num : nums) {
            if ((num & right_digit_diff) == 0) {
                single_num1 ^= num;
            } else {
                single_num2 ^= num;
            }
        }

        return {single_num1, single_num2};
    }
};