Missing Number
Part of Practice: Arithmetic Without +
You are given an array nums containing n distinct numbers, each drawn from the range 0 to n inclusive. That range holds n + 1 possible values but the array only has room for n of them, so exactly one value from the range is missing. Return the missing value.
Sorting or a hash set solves it easily, but the follow-up asks for O(n) time with O(1) extra space.
Examples
- Input:
- nums = [3, 0, 1]
- Output:
- 2
n = 3, so the full range is 0..3. Of those, 2 is the only value not present.
- Input:
- nums = [0, 1]
- Output:
- 2
n = 2 and the range is 0..2; the missing value can be n itself.
- Input:
- nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
- Output:
- 8
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.