Missing Number
Medium · rating 1200 · arrays, math
The first line contains n. The second line contains n distinct integers from the range 0 to n with exactly one missing. Print the missing number.
Editorial
Approach
The values should form a full 0..n range with exactly one gap. The sum of 0..n is n(n+1)/2; subtract the actual array sum and what's left is the missing value.
n = len(nums)
return n*(n+1)//2 - sum(nums)Alternative
XOR-ing all indices 0..n with all the values also cancels every present number and leaves the missing one — handy if the sum might overflow.
Complexity
Time: O(n). Space: O(1).