Find Missing Number 1 to n

Given a list with numbers from 1 to n missing exactly one value, find the missing one efficiently.

arrays math search

Write a function `find_missing(nums)` that takes a list of integers `nums` and returns the missing number.

The list contains exactly `n-1` distinct integers, each between 1 and `n` inclusive, where `n` is the length of the list plus one. There is exactly one number missing from the range 1..n.

You must return the missing integer. Your solution should be efficient in both time and space.

For example, if the input is `[3, 1, 4]`, then the full range is 1..4 and the missing number is 2.

Constraints

Input length is between 1 and 10^5.
The list contains distinct integers in the range [1, n] (exactly one missing).
Return the missing integer.
Expected time complexity O(n), space complexity O(1).

Example

>>> find_missing([3, 1, 4])
2
>>> find_missing([1])
2
>>> find_missing([2, 3, 4])
1

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

What is the sum of all numbers from 1 to n?

Subtract the sum of the given numbers from the total sum.

The total sum is n*(n+1)//2 where n is len(nums)+1.

Test Results

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