Single Number III

How it works

This approach is similar to the previous one but uses a neat trick to find the rightmost set bit. The expression x & (-x) isolates the lowest set bit in x. Using this on the XOR of all numbers immediately gives us a differing bit between the two unique numbers without looping.

Steps

1. XOR all numbers to get a ^ b.
2. Compute diff_bit = xor & (-xor) to get the rightmost set bit.
3. Partition numbers based on whether they have this bit set.
4. XOR within each partition to find a and b.
5. Return both unique numbers.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Confusing This Problem with Single Number I

Unlike the classic Single Number problem where XORing all elements directly yields the answer, this problem has two unique numbers. XORing all elements gives a ^ b, not the individual values. Candidates often fail to recognize that an additional step is needed to separate the two numbers.

Misunderstanding the Differing Bit Logic

The key insight is that a ^ b has at least one set bit where a and b differ. Using this bit to partition the array into two groups is crucial. A common mistake is not understanding why this partitioning works or incorrectly identifying which bit to use for separation.

Integer Overflow When Finding the Rightmost Set Bit

The expression x & (-x) to find the rightmost set bit can cause overflow issues in some languages when dealing with the minimum integer value. In languages like C++ or Java, negating INT_MIN causes undefined behavior or overflow, requiring careful handling with unsigned types or alternative approaches.

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num

        diff_bit = xor & (-xor)

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

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        uint xor_all = 0;
        for (int& num : nums) {
            xor_all ^= num;
        }

        int diff_bit = xor_all & (-xor_all);

        int a = 0, b = 0;
        for (int& num : nums) {
            if (num & diff_bit) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return {a, b};
    }
};