Find Missing Number

Find the one missing integer from 0 to n using a simple formula.

math integers arrays logic

Write a function `find_missing_number(nums)` that accepts a list `nums` containing `n` distinct integers taken from the range `0` to `n` inclusive (so there are `n+1` numbers in that range, but the list has only `n` of them). Exactly one number from the range is missing. Return the missing integer.

You must not modify the input list. The solution should be efficient; using the sum formula is a good approach.

Constraints

Input length n satisfies 0 <= n <= 10^5. All numbers are distinct and lie between 0 and n inclusive. The list may be empty (which means the only number in the range 0..0 that is missing is 0). The function should run in O(n) time and O(1) extra space.

Example

>>> find_missing_number([3, 0, 1])
2
>>> find_missing_number([0, 1])
2
>>> find_missing_number([9,6,4,2,3,5,7,0,1])
8
>>> find_missing_number([])
0

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

If all numbers from 0 to n were present, what would the sum be? Use the arithmetic series formula.

The sum of 0 + 1 + ... + n is n * (n + 1) // 2.

Subtract the sum of the given numbers from the expected sum. The difference is the missing number.

Be careful: n = len(nums). For the empty list, expected sum is 0 and the sum of nums is 0, so the missing number is 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.