Math & Bits · 089Easy
Missing Number
Given an array nums containing n distinct numbers drawn from the range [0, n], return the one number in that range that is missing. Aim for O(n) time and O(1) extra space.
Constraints
- n == nums.length, 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All values are unique.
Examples
missingNumber([3, 0, 1]) -> 2 missingNumber([0, 1]) -> 2 // the missing one can be n itself missingNumber([9,6,4,2,3,5,7,0,1]) -> 8 missingNumber([0]) -> 1 // n = 1, the top of the range is gone missingNumber([1]) -> 0 // n = 1, 0 is the one missing missingNumber([2, 0]) -> 1 // missing from the middle
Edge cases
- The missing value may be 0 or n, at either end of the range.
- FOLLOW-UP
- A Set solution is O(n) space and misses the target.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — sort and find the first index-value mismatch.
- Target
- O(n) time, O(1) space — either XOR all indices with all values, or subtract the array sum from n(n+1)/2.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/12-math-bits/089-missing-number.js ./practice c 089