Missing Number
Given an array containing n distinct numbers in the range [0, n], find the one number that is missing from the array.
This problem demonstrates both a sorting approach and an elegant mathematical alternative. The sorting approach shows how sorted data makes gaps easy to spot.
Input
nums: a list of n distinct integers from the range [0, n]
Output
An integer representing the missing number from the range
Examples
Example 1:
Input: nums = [3, 0, 1]
Output: 2
Explanation:
- n = 3 since there are 3 numbers, so the range is [0, 3]
- After sorting: [0, 1, 3]
- Position 0 has value 0 (correct)
- Position 1 has value 1 (correct)
- Position 2 has value 3 (expected 2), so 2 is missing
Example 2:
Input: nums = [0, 1]
Output: 2
Explanation:
- n = 2 since there are 2 numbers, so the range is [0, 2]
- After sorting: [0, 1]
- All positions match their values, so n itself (2) is missing
Example 3:
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation:
- n = 9, range is [0, 9]
- After sorting: [0, 1, 2, 3, 4, 5, 6, 7, 9]
- Position 8 has value 9 (expected 8), so 8 is missing