Problem Description

You are given an integer array nums where exactly two elements appear only once and all the other elements appear exactly twice. Your task is to find the two elements that appear only once and return them in any order.

• Each input will have exactly one valid solution.
• You must not reuse elements from the array as answers.
• Try to solve the problem with linear runtime complexity and constant extra space.

Thought Process

At first glance, the problem seems similar to the classic "Single Number" problem, where every element appears twice except for one. There, we could use XOR to find the unique element. However, here we have two unique numbers, so the direct application of XOR will not immediately give us both.

A brute-force approach would be to use a hash map or count array to count the frequency of each number, then return the numbers that appear once. While this works, it uses extra space and doesn't take advantage of bitwise properties.

The challenge is to find a way to separate the two unique numbers using the properties of XOR, which is both space and time efficient. The key insight is that XOR-ing all numbers gives us the XOR of the two unique numbers, and we can use this result to distinguish between them.

Solution Approach

We can solve this problem efficiently using bit manipulation and the properties of XOR. Here's a step-by-step breakdown:

1. XOR all numbers: If we XOR all elements in nums, all numbers that appear twice will cancel out (since a ^ a = 0), leaving us with xor = a ^ b, where a and b are the two unique numbers.
2. Find a distinguishing bit: Since a and b are different, xor is non-zero. Find any bit that is set (1) in xor (e.g., rightmost set bit). This bit must be different between a and b.
3. Partition numbers: Use the found bit to partition all numbers into two groups: those with that bit set, and those without. Each group will contain one of the unique numbers and pairs of duplicate numbers.
4. XOR within groups: XOR all numbers in each group separately. Duplicate numbers will cancel out, and each group will be left with one of the unique numbers.

This approach only requires a few variables (constant space) and a few passes over the array (linear time).

Example Walkthrough

Let's walk through an example with nums = [1, 2, 1, 3, 2, 5]:

1. XOR all numbers:
   1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5 = 0 ^ 0 ^ 3 ^ 5 = 3 ^ 5 = 6
2. Find a set bit in 6:
   6 in binary is 110. The rightmost set bit is at position 2 (value 2).
3. Partition numbers by this bit:
   • Group 1 (bit set): numbers where bit 2 is set: 2, 2, 3
   • Group 2 (bit not set): 1, 1, 5
4. XOR each group:
   • Group 1: 2 ^ 2 ^ 3 = 0 ^ 3 = 3
   • Group 2: 1 ^ 1 ^ 5 = 0 ^ 5 = 5

   The two unique numbers are 3 and 5.

Time and Space Complexity

• Brute-force approach: Using a hash map to count elements takes O(n) time and O(n) space, where n is the length of nums.
• Optimized bit manipulation approach:
  • Time Complexity: O(n), since we iterate over the array a constant number of times.
  • Space Complexity: O(1), as we use only a few variables for calculations, regardless of the input size.

Summary

The "Single Number III" problem is elegantly solved by leveraging the XOR operation to cancel out duplicate numbers and isolate the two unique numbers. By identifying a bit where the two unique numbers differ, we can partition the array and extract each unique number separately with further XOR operations. This approach is both time and space efficient, requiring only linear time and constant space, and demonstrates the power of bit manipulation for problems involving pairs and unique elements.

Code Implementation

class Solution:
    def singleNumber(self, nums):
        xor_all = 0
        for num in nums:
            xor_all ^= num

        # Find rightmost set bit
        diff = xor_all & -xor_all

        a = 0
        b = 0
        for num in nums:
            if num & diff:
                a ^= num
            else:
                b ^= num
        return [a, b]
      

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for (int num : nums) xor_all ^= num;
        int diff = xor_all & -xor_all;
        int a = 0, b = 0;
        for (int num : nums) {
            if (num & diff) a ^= num;
            else b ^= num;
        }
        return {a, b};
    }
};
      

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int num : nums) xorAll ^= num;
        int diff = xorAll & -xorAll;
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & diff) != 0) a ^= num;
            else b ^= num;
        }
        return new int[]{a, b};
    }
}
      

var singleNumber = function(nums) {
    let xorAll = 0;
    for (const num of nums) xorAll ^= num;
    let diff = xorAll & -xorAll;
    let a = 0, b = 0;
    for (const num of nums) {
        if (num & diff) a ^= num;
        else b ^= num;
    }
    return [a, b];
};