# LeetCode 136: Single Number

## Problem Restatement

We are given a non-empty integer array `nums`.

Every element appears exactly twice except for one element.

We need to return the element that appears only once.

The solution must run in linear time and use constant extra space. LeetCode states this explicitly in the problem requirements.

## Examples

Example 1:

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

The number `2` appears twice.

The number `1` appears once.

Output:

```python
1
```

Example 2:

```python
nums = [4, 1, 2, 1, 2]
```

The numbers `1` and `2` appear twice.

The number `4` appears once.

Output:

```python
4
```

Example 3:

```python
nums = [1]
```

There is only one number, so it is the answer.

Output:

```python
1
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums: list[int]` |
| Output | The integer that appears once |
| Rule | Every other integer appears exactly twice |
| Required time | `O(n)` |
| Required space | `O(1)` |

Function shape:

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

## First Thought: Count Frequencies

A simple solution is to count how many times each number appears.

For example:

```python
nums = [4, 1, 2, 1, 2]
```

The counts are:

| Number | Count |
|---:|---:|
| `4` | `1` |
| `1` | `2` |
| `2` | `2` |

Then we return the number with count `1`.

This works, but it uses a hash map.

The space complexity is `O(n)`, so it violates the constant-space requirement.

## Key Insight

Use XOR.

XOR has three useful properties:

| Rule | Meaning |
|---|---|
| `x ^ x = 0` | A number cancels itself |
| `x ^ 0 = x` | Zero does not change a number |
| Order does not matter | We can XOR numbers in any order |

So if we XOR every number in the array, all duplicate pairs cancel out.

For example:

```text
4 ^ 1 ^ 2 ^ 1 ^ 2
```

Reorder mentally:

```text
(1 ^ 1) ^ (2 ^ 2) ^ 4
```

The duplicate pairs become zero:

```text
0 ^ 0 ^ 4 = 4
```

So the remaining value is the single number.

## Algorithm

Initialize:

```python
answer = 0
```

Then scan every number:

```python
answer ^= num
```

At the end, return `answer`.

## Correctness

Every number except one appears exactly twice.

When a duplicate number is XORed with itself, it becomes `0`.

Because XOR is associative and commutative, the order of operations does not affect the final result.

Therefore, all paired numbers cancel out.

The only number that does not have a matching pair remains in the final XOR result.

So the algorithm returns exactly the single number.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We keep only one integer variable |

## Implementation

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

        for num in nums:
            answer ^= num

        return answer
```

## Code Explanation

Start from zero:

```python
answer = 0
```

This works because XOR with zero keeps the number unchanged.

Then process each number:

```python
for num in nums:
    answer ^= num
```

Each duplicate pair cancels itself.

After the loop, only the single number remains:

```python
return answer
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.singleNumber([2, 2, 1]) == 1
    assert s.singleNumber([4, 1, 2, 1, 2]) == 4
    assert s.singleNumber([1]) == 1
    assert s.singleNumber([-1, 2, 2]) == -1
    assert s.singleNumber([0, 1, 0]) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 2, 1]` | Basic duplicate pair |
| `[4, 1, 2, 1, 2]` | Single number appears first |
| `[1]` | Minimum input size |
| `[-1, 2, 2]` | Negative number |
| `[0, 1, 0]` | Zero participates in duplicate cancellation |