# LeetCode 268: Missing Number

## Problem Restatement

We are given an array `nums` containing `n` distinct numbers from the range:

```python
0, 1, 2, ..., n
```

Exactly one number from this range is missing.

Return the missing number.

For example, if:

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

then `n = 3`, so the full range should be:

```python
[0, 1, 2, 3]
```

The missing number is:

```python
2
```

The problem asks for an algorithm with linear runtime. The common follow-up is to use only constant extra space.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array `nums` of length `n` |
| Output | The missing number |
| Range | Numbers should come from `0` to `n` |
| Property | All given numbers are distinct |

Example function shape:

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

## Examples

Example 1:

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

The complete range is:

```python
[0, 1, 2, 3]
```

The missing number is:

```python
2
```

Answer:

```python
2
```

Example 2:

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

The complete range is:

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

The missing number is:

```python
2
```

Answer:

```python
2
```

Example 3:

```python
nums = [9,6,4,2,3,5,7,0,1]
```

The complete range is:

```python
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

The missing number is:

```python
8
```

Answer:

```python
8
```

## First Thought: Use a Set

A simple solution stores all numbers in a set.

Then check each value from `0` to `n`.

```python
class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        seen = set(nums)

        for x in range(len(nums) + 1):
            if x not in seen:
                return x

        return -1
```

This is easy and correct, but it uses extra space.

## Problem With the Set Solution

The set stores up to `n` numbers.

So the space complexity is:

```python
O(n)
```

We can solve the problem using only arithmetic.

## Key Insight

The numbers should contain every value from `0` to `n`, except one.

The sum of the complete range is:

```python
0 + 1 + 2 + ... + n
```

This sum has a direct formula:

```python
n * (n + 1) // 2
```

If we subtract the actual sum of `nums`, the remaining value is the missing number.

## Algorithm

1. Let `n = len(nums)`.
2. Compute the expected sum:
   ```python id="t4s5eb"
   expected = n * (n + 1) // 2
   ```
3. Compute the actual sum:
   ```python id="lbvfc3"
   actual = sum(nums)
   ```
4. Return:
   ```python id="yr4s6x"
   expected - actual
   ```

## Walkthrough

Use:

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

The array length is:

```python
n = 3
```

Expected sum:

```python
3 * (3 + 1) // 2 = 6
```

Actual sum:

```python
3 + 0 + 1 = 4
```

Difference:

```python
6 - 4 = 2
```

Return:

```python
2
```

## Correctness

The complete range `0` through `n` contains every valid number exactly once.

The input array contains the same range except for one missing value.

So:

```python
expected_sum = actual_sum + missing
```

Rearranging gives:

```python
missing = expected_sum - actual_sum
```

The algorithm computes exactly this difference.

Therefore it returns the missing number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Computing `sum(nums)` scans the array once |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        expected = n * (n + 1) // 2
        actual = sum(nums)

        return expected - actual
```

## Code Explanation

The value `n` is the array length:

```python
n = len(nums)
```

Since the numbers come from `0` to `n`, the complete range contains `n + 1` numbers.

The expected sum is:

```python
expected = n * (n + 1) // 2
```

The actual sum is:

```python
actual = sum(nums)
```

The missing number is the difference:

```python
return expected - actual
```

## Alternative: XOR Solution

We can also solve this with XOR.

XOR has these useful properties:

```python
x ^ x = 0
x ^ 0 = x
```

If we XOR all numbers from `0` to `n`, and also XOR all numbers in `nums`, every present number cancels out.

Only the missing number remains.

```python
class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        missing = len(nums)

        for i, x in enumerate(nums):
            missing ^= i
            missing ^= x

        return missing
```

For example:

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

Start with:

```python
missing = 3
```

Then XOR indices and values:

```python
3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1
```

All matching values cancel.

The result is:

```python
2
```

## Testing

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

    assert s.missingNumber([3, 0, 1]) == 2
    assert s.missingNumber([0, 1]) == 2
    assert s.missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
    assert s.missingNumber([0]) == 1
    assert s.missingNumber([1]) == 0
    assert s.missingNumber([1, 2, 3]) == 0
    assert s.missingNumber([0, 1, 2]) == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3, 0, 1]` | Standard middle missing value |
| `[0, 1]` | Missing value is `n` |
| Long unsorted input | Confirms order does not matter |
| `[0]` | Single value, missing upper bound |
| `[1]` | Single value, missing zero |
| `[1, 2, 3]` | Missing lower bound |
| `[0, 1, 2]` | Missing upper bound |