Solution Explanation for LeetCode 260: Single Number III

This problem requires finding two unique numbers in an array where all other numbers appear twice. The constraints demand a linear time and constant space solution, ruling out simple hash table approaches which would use O(n) space. The optimal solution leverages bit manipulation.

Approach 1: Bitwise XOR and Lowbit

This approach cleverly uses the properties of the XOR operation:

1. XORing all numbers: The XOR operation is commutative and associative. If we XOR all numbers in the array, numbers that appear twice will cancel each other out (x ^ x = 0). The final result will be the XOR of the two unique numbers (let's call them a and b). a ^ b will be non-zero.

2. Finding the differentiating bit: We find the least significant bit (LSB) that is set to 1 in a ^ b. This bit is crucial because it indicates a difference between a and b. We use the lowbit trick (x & -x) to efficiently find this LSB.

3. Grouping and XORing again: We iterate through the array again. If a number has the LSB (found in step 2) set to 1, it belongs to one group; otherwise, it's in the other group. By XORing all numbers within each group, we isolate a and b.

Time Complexity: O(n) - We iterate through the array twice. Space Complexity: O(1) - We only use a few integer variables.

Code Examples:

The code implementations in various languages follow the algorithm described above. Here are a few examples:

Python:

def singleNumber(nums):
    xs = 0
    for x in nums:
        xs ^= x
    lb = xs & -xs
    a = 0
    for x in nums:
        if x & lb:
            a ^= x
    b = xs ^ a
    return [a, b]
 

Java:

class Solution {
    public int[] singleNumber(int[] nums) {
        int xs = 0;
        for (int x : nums) xs ^= x;
        int lb = xs & -xs;
        int a = 0;
        for (int x : nums) if ((x & lb) != 0) a ^= x;
        int b = xs ^ a;
        return new int[] {a, b};
    }
}

C++:

vector<int> singleNumber(vector<int>& nums) {
    int xs = 0;
    for (int x : nums) xs ^= x;
    int lb = xs & -xs;
    int a = 0;
    for (int x : nums) if (x & lb) a ^= x;
    int b = xs ^ a;
    return {a, b};
}

Approach 2: Hash Table (Less Efficient)

A simpler but less efficient approach (violating the space complexity constraint) would use a hash table (or Set in Python/Java/JavaScript):

1. Iterate and count: Iterate through the array. For each number, check if it's in the hash table. If not, add it with a count of 1. If it is, increment its count.
2. Filter uniques: After iterating, filter the hash table to find entries with a count of 1. These are the unique numbers.

Time Complexity: O(n) Space Complexity: O(n) - The hash table stores up to n/2 elements in the worst case. This is not optimal for the problem's requirements.

This approach is easier to understand but less efficient in terms of space complexity compared to the bit manipulation approach. Therefore, the bit manipulation method is preferred for this LeetCode problem.