Missing Number in Array
Given an array containing n distinct numbers taken from 0 to n, find the one number that is missing from the array. For instance, given the array [3, 0, 1], the number 2 is missing. Your solution should run in linear runtime complexity and use only constant extra space.
[ [ 3, 0, 1 ] ]
Explanation. The sum of numbers from `0` to `3` is `6` and the sum of the array `[3, 0, 1]` is `4`. Hence, the missing number is `6 - 4 = 2`.
[ [ 9, 6, 4, 2, 3, 5, 7, 0, 1 ] ]
Explanation. The sum of numbers from `0` to `9` is `45` and the sum of the array `[9,6,4,2,3,5,7,0,1]` is `37`. Therefore, the missing number is `45 - 37 = 8`.
[ [ 0 ] ]
Explanation. The expected number should be `1` as it's the missing number when considering the range from `0` to `1`.
Follow-up: Can you implement a solution using a mathematical formula to compute the missing number directly?
The length of the array is at least 1 and at most 10,000. All elements are unique.
- Views
- 19