Missing Number

Find All Anagrams in a String

Kth Smallest Element in a Sorted Matrix

Find the only value missing from the distinct numbers drawn from the range 0 through n.

You are given an array `nums` containing `n` distinct numbers taken from the range `0` through `n`.

Exactly one value in that range is missing. Return the missing number.

**Input / output**
- Input: `nums: int[]`
- Output: the missing integer in `[0, n]`

**Examples**
1. `nums = [3, 0, 1]` returns `2`.
2. `nums = [0, 1]` returns `2`.
3. `nums = [9,6,4,2,3,5,7,0,1]` returns `8`.

**Constraints**
- `1 <= nums.length <= 100000`
- `0 <= nums[i] <= nums.length`
- All values in `nums` are distinct.

**Edge cases**
- The missing value may be `0`.
- The missing value may be `n` itself.
- The input is not guaranteed to be sorted.

**Target complexity**
- Aim for `O(n)` time and `O(1)` extra space.

**Hints**
1. Compare the expected sum of `0 + 1 + ... + n` with the actual array sum.
2. The XOR trick also works because equal values cancel each other.

**Follow-up**
What other constant-space approach can you derive using XOR instead of arithmetic sums?

- The numbers must be exactly the values from `0` to `n`, except one missing entry.
- That guarantee gives a closed-form expectation we can compare against the actual array.

Use the range guarantee

- For every value from `0` through `n`, scan the array to see whether it exists.
- This works, but the nested search costs `O(n^2)` time.

Brute-force membership checks

- The full range `0..n` sums to `n * (n + 1) / 2`.
- Since exactly one value is missing and nothing is duplicated, subtracting the actual array sum reveals that missing value immediately.

Compare expected and actual totals

- First compute the expected range sum.
- Then subtract every number in the array and return the remainder.

Compute the missing value in one pass

Trace `nums = [3, 0, 1]`.

| quantity | value |
|---|---:|
| `n` | `3` |
| expected sum `0 + 1 + 2 + 3` | `6` |
| actual array sum `3 + 0 + 1` | `4` |
| missing number `expected - actual` | `2` |

Because the array contains distinct numbers, no extra bookkeeping is needed beyond the running total.

Dry run / arithmetic trace

The sum formula finds the missing value in `O(n)` time and `O(1)` extra space.