# LeetCode 260: Single Number III

## Problem Restatement

We are given an integer array `nums`.

Exactly two numbers appear only once.

Every other number appears exactly twice.

We need to return the two numbers that appear only once.

The answer may be returned in any order.

The problem asks for:

- Linear runtime
- Constant extra space

The constraints are `2 <= nums.length <= 3 * 10^4`, `-2^31 <= nums[i] <= 2^31 - 1`. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0200-0299/0260.Single%20Number%20III/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | The two numbers appearing once |
| Duplicate rule | Every other number appears exactly twice |
| Goal | `O(n)` time and `O(1)` extra space |

Example function shape:

```python
def singleNumber(nums: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 1, 3, 2, 5]
```

Numbers `1` and `2` appear twice.

Numbers `3` and `5` appear once.

Answer:

```python
[3, 5]
```

Example 2:

```python
nums = [-1, 0]
```

Both numbers appear once.

Answer:

```python
[-1, 0]
```

Example 3:

```python
nums = [0, 1]
```

Both numbers appear once.

Answer:

```python
[0, 1]
```

## First Thought: Count Frequencies

A direct solution uses a hash map.

Count how many times each number appears.

Then return the numbers with count `1`.

```python
class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        freq = {}

        for x in nums:
            freq[x] = freq.get(x, 0) + 1

        ans = []

        for x, count in freq.items():
            if count == 1:
                ans.append(x)

        return ans
```

This works, but it uses extra memory.

## Problem With Hash Maps

The follow-up requires constant extra space.

A frequency table needs:

$$
O(n)
$$

space in the worst case.

We need to exploit the structure of the problem instead.

The key observation is that every duplicated number appears exactly twice.

That strongly suggests XOR.

## XOR Properties

XOR has two critical properties:

| Property | Meaning |
|---|---|
| `x ^ x = 0` | A number cancels itself |
| `x ^ 0 = x` | Zero changes nothing |

For example:

```python
1 ^ 1 = 0
5 ^ 5 = 0
```

So if we XOR the entire array:

```python
xor_all = a ^ b
```

all duplicated numbers disappear.

Only the two unique numbers remain.

Suppose:

```python
a = 3
b = 5
```

Then:

```python
3 ^ 5 = 6
```

Binary:

```text
3 = 011
5 = 101
-----------
    110
```

The XOR result contains bits where `a` and `b` differ.

## Key Insight

If two numbers differ at some bit position, then:

- One has bit `0`
- The other has bit `1`

We can use one differing bit to separate the array into two groups.

Inside each group:

- Duplicate numbers still appear twice, so they cancel out.
- The two unique numbers go into different groups.

Then XOR inside each group gives the answer.

## Finding a Differing Bit

Suppose:

```python
xor_all = a ^ b
```

Since `a != b`, at least one bit is set in `xor_all`.

We isolate one set bit using:

```python
diff = xor_all & -xor_all
```

This extracts the rightmost set bit.

For example:

```text
xor_all = 6 = 110
-diff representation isolates:
diff = 010
```

Now we partition numbers by whether this bit is set.

## Algorithm

1. XOR all numbers together.
2. The result becomes:
   ```python id="8fzvqo"
   xor_all = a ^ b
   ```
3. Extract one differing bit:
   ```python id="jlwm9w"
   diff = xor_all & -xor_all
   ```
4. Partition the array into two groups:
   - Bit set
   - Bit not set
5. XOR numbers inside each group.
6. Duplicate values cancel out.
7. The remaining values are the two answers.

## Walkthrough

Use:

```python
nums = [1, 2, 1, 3, 2, 5]
```

### Step 1: XOR Everything

Compute:

```python
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
```

Pairs cancel:

```python
(1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 5)
```

Result:

```python
0 ^ 0 ^ 6 = 6
```

So:

```python
xor_all = 6
```

Binary:

```text
6 = 110
```

### Step 2: Extract One Set Bit

```python
diff = xor_all & -xor_all
```

Result:

```python
diff = 2
```

Binary:

```text
010
```

### Step 3: Partition Numbers

Group 1: bit set

```python
2, 3, 2
```

Group 2: bit not set

```python
1, 1, 5
```

### Step 4: XOR Each Group

Group 1:

```python
2 ^ 3 ^ 2 = 3
```

Group 2:

```python
1 ^ 1 ^ 5 = 5
```

Answer:

```python
[3, 5]
```

## Correctness

Let the two unique numbers be `a` and `b`.

XORing the entire array cancels every duplicated number because:

$$
x \oplus x = 0
$$

So the total XOR becomes:

$$
xor_{all} = a \oplus b
$$

Since `a != b`, at least one bit in `xor_all` is set.

The value:

```python
diff = xor_all & -xor_all
```

isolates one such differing bit.

At this bit position:

- One of `a` and `b` has bit `1`
- The other has bit `0`

Therefore `a` and `b` are placed into different groups.

Every duplicated number appears twice with identical bits, so both copies enter the same group and cancel under XOR.

After XORing each group separately, only the unique number from that group remains.

Thus the algorithm returns exactly the two numbers appearing once.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Two linear scans |
| Space | `O(1)` | Only a few variables |

## Implementation

```python
class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        xor_all = 0

        for x in nums:
            xor_all ^= x

        diff = xor_all & -xor_all

        a = 0
        b = 0

        for x in nums:
            if x & diff:
                a ^= x
            else:
                b ^= x

        return [a, b]
```

## Code Explanation

First compute the XOR of the full array:

```python
xor_all ^= x
```

All duplicated values cancel out.

The result becomes:

```python
a ^ b
```

Next isolate one differing bit:

```python
diff = xor_all & -xor_all
```

This bit separates the two unique numbers.

We create two XOR accumulators:

```python
a = 0
b = 0
```

Then partition numbers using the extracted bit:

```python
if x & diff:
```

Numbers with the bit set go into one group.

Others go into the second group.

Inside each group, duplicates cancel, leaving exactly one unique number.

Finally return both results.

## Testing

```python
def normalize(ans: list[int]) -> list[int]:
    return sorted(ans)

def run_tests():
    s = Solution()

    assert normalize(s.singleNumber([1, 2, 1, 3, 2, 5])) == [3, 5]
    assert normalize(s.singleNumber([-1, 0])) == [-1, 0]
    assert normalize(s.singleNumber([0, 1])) == [0, 1]
    assert normalize(s.singleNumber([4, 1, 2, 1, 2, 5])) == [4, 5]
    assert normalize(s.singleNumber([7, 7, 8, 9])) == [8, 9]
    assert normalize(s.singleNumber([-3, -3, -1, -2])) == [-2, -1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Basic XOR partitioning |
| Negative values | Confirms signed integer handling |
| Zero values | Checks zero inside XOR |
| Mixed duplicates | General correctness |
| Two unique positives | Simple separation |
| Negative unique numbers | Bit partitioning with negatives |