You are given an integer array where every element appears exactly twice except for two elements which appear only once.
Your task is to return those two unique numbers.

Example:

Input: [1,2,1,3,2,5]
Output: [3,5]
Explanation:
Numbers 1 and 2 appear twice.
Numbers 3 and 5 appear once.

Order does not matter.

---

Understanding the Problem

This is a variation of the classic “single number” XOR problem.
In earlier versions (like problem 136), exactly one number appears once, and everything else appears twice.

Here, two numbers appear once.

The challenge is to find both unique numbers in an efficient way without using extra space like HashMaps or sorting.

---

Approach (Explained in Simple Language)

XOR properties make this problem very easy:

1. XOR of a number with itself is 0
2. XOR of a number with 0 is the number
3. XOR is commutative and associative

Using these properties:

Step 1: XOR all numbers

All duplicates cancel out (because x ^ x = 0).
The result becomes XOR of the two unique numbers:

xor = a ^ b

where a and b are the two unique values.

But xor alone does not tell us what a and b individually are.

Step 2: Find a differentiating bit

Since a and b are different, their XOR has at least one bit set to 1.
Pick the rightmost set bit (xor & -xor).

This bit helps separate numbers into two groups:

Group 1: numbers where this bit is 1
Group 2: numbers where this bit is 0

The two unique numbers fall into different groups.

Step 3: XOR numbers inside each group

All duplicate numbers still cancel out, leaving only one unique number in each group.

This gives the two answers.

Time complexity = O(n)
Space complexity = O(1)

---

Java Code

public class SingleNumberIII {

    public int[] singleNumber(int[] nums) {

        int xor = 0;

        for (int num : nums) {
            xor ^= num;
        }

        int rightmostSetBit = xor & -xor;

        int a = 0;
        int b = 0;

        for (int num : nums) {
            if ((num & rightmostSetBit) != 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }

    public static void main(String[] args) {
        SingleNumberIII solution = new SingleNumberIII();
        int[] result = solution.singleNumber(new int[]{1,2,1,3,2,5});
        System.out.println(result[0] + " " + result[1]);
    }
}

---

Dry Run

Input:
nums = [1, 2, 1, 3, 2, 5]

---

Step 1: XOR all numbers

xor = 0
xor ^= 1 → 1
xor ^= 2 → 3
xor ^= 1 → 2
xor ^= 3 → 1
xor ^= 2 → 3
xor ^= 5 → 6

Final xor = 6

Binary form:
6 = 110
This means the two unique numbers differ in at least these bits.

---

Step 2: Find rightmost set bit

rightmostSetBit = xor & -xor
rightmostSetBit = 6 & (-6)

6 = 110
-6 (two’s complement) = 010

rightmostSetBit = 010 (decimal 2)

This bit is where the two unique numbers differ.

---

Step 3: Divide into two groups and XOR inside each group

rightmostSetBit = 2 → binary 010

Process each number:

1: 001 & 010 = 0 → Group B → b ^= 1 → b = 1
2: 010 & 010 = 1 → Group A → a ^= 2 → a = 2
1: 001 & 010 = 0 → Group B → b ^= 1 → b = 0
3: 011 & 010 = 1 → Group A → a ^= 3 → a = 1
2: 010 & 010 = 1 → Group A → a ^= 2 → a = 3
5: 101 & 010 = 0 → Group B → b ^= 5 → b = 5

Final:

a = 3
b = 5

These are the two unique numbers.

---

Why This Approach Works

All duplicates cancel out using XOR.
The rightmost set bit ensures that the two unique numbers fall into different groups.
Within each group, only one number appears once; the rest appear twice and cancel out.

This gives the answer in linear time and constant space.