Single Number III

Problem Link

Problem Statement

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice, return the two elements that appear only once.

You can return the answer in any order.

Examples

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: 3 and 5 appear only once; others appear twice.

Example 2:

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

Constraints

2 <= nums.length <= 3 * 10⁴
All elements in nums are integers within the 32-bit signed integer range
Exactly two numbers appear once, others appear twice

Intuition

If only one number appeared once, XOR of all elements would give that number (since x ^ x = 0 and x ^ 0 = x).

With two unique numbers, say a and b, their XOR gives:

a ^ b = x (non-zero)

This x must have at least one set bit → that set bit differs between a and b.
We use this distinguishing bit to divide the array into two groups:

One group where that bit is 0
Another group where that bit is 1

Since all other numbers appear twice, XORing each group separately will isolate a and b.

Approach: Bit Partition Using Rightmost Set Bit

XOR all elements → get xor = a ^ b
(Since all other elements cancel out)
Find the rightmost set bit in xor:
```
int diffBit = xor & (-xor);
```
This isolates the lowest bit where a and b differ
Split the numbers into two groups based on diffBit:
- One where i & diffBit == 0
- Other where i & diffBit != 0
XOR each group separately → will give the two single numbers

Java Code

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }

        int diffBit = xor & -xor; // Rightmost set bit
        int x = 0, y = 0;

        for (int i : nums) {
            if ((i & diffBit) == 0) {
                x ^= i;
            } else {
                y ^= i;
            }
        }

        return new int[]{x, y};
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)
Explanation	One pass for total XOR, one pass for splitting — all in constant space

Dry Run

Input: `[1, 2, 1, 3, 2, 5]`

Step 1: xor = 3 ^ 5 = 6 (binary 0110)
Step 2: diffBit = 2 (binary 0010)
Partition:
- Group 1 (bit unset): 1, 1, 3 → XOR = 3
- Group 2 (bit set): 2, 2, 5 → XOR = 5

Output: [3, 5]

Conclusion

This problem is a smart extension of the XOR trick used in "Single Number" problems. It beautifully demonstrates:

Using XOR to cancel out duplicate numbers
Leveraging bitmasking to split the problem into two independent subproblems
Efficient linear-time solution with constant space