#LC 268•Arrays & Hashing•Easy
Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Understand the problem
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1
Input: nums = [3, 0, 1]
Output: 2
The expected range is [0, 1, 2, 3]. The array has 0, 1 and 3, so 2 is missing.
Example 2
Input: nums = [0, 1]
Output: 2
The expected range is [0, 1, 2]. The number 2 is missing.
Example 3
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
The expected range is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. Only 8 is absent.
Constraints
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All numbers in nums are unique.
- Exactly one number in the range [0, n] is missing.
Think first
The numbers should cover every value from 0 to n. How can we find the one that is absent without sorting?
Pattern tags:Bit ManipulationXOR CancellationRunning Accumulator