Find Missing Number
easySave
ArrayBit ManipulationMath
Given an array containing n distinct numbers taken from 0 to n, find the one number that is missing from the array.
Example 1
Input
[ [ 3, 0, 1 ] ]
Output
2
Explanation. The numbers from 0 to 3 are 0, 1, 2, 3. The number missing from input array [3, 0, 1] is 2.
Example 2
Input
[ [ 0, 1 ] ]
Output
2
Explanation. The numbers from 0 to 2 are 0, 1, 2. The number missing from input array [0, 1] is 2.
Example 3
Input
[ [ 9, 6, 4, 2, 3, 5, 7, 0, 1 ] ]
Output
8
Explanation. The numbers from 0 to 9 are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The number missing from input array [9,6,4,2,3,5,7,0,1] is 8.
Example 4
Input
[ [ 0 ] ]
Output
1
Explanation. The numbers from 0 to 1 are 0, 1. The number missing from input array [0] is 1.
Follow-up: Can you implement a solution using O(n) time complexity and O(1) space complexity?
Constraints:
The array will contain at least one element and at most 10000 elements. All elements are non-negative integers.
- Views
- 3