The missing number
Someone wrote down every whole number from 0 to n, each once, and then lost one of them. The list nums holds the n numbers that are left, in any order. Return the lost number as an int.
You are not given n separately: n + 1 numbers minus the lost one leaves n, so n is len(nums).
Checking each candidate from 0 to n with in is correct but fails the speed test. Aim for O(n) time and O(1) extra space. The tests can check only the time.
nums = [4, 2, 0, 1]Output3n is 4, so the values should be 0 to 4. 3 is not in the list.
nums = [1, 2]Output0n is 2, so the values should be 0, 1 and 2. 0 is missing.
nums = [0]Output1n is 1, so the values should be 0 and 1. The missing value can be n itself.
1 ≤ n = len(nums) ≤ 105
0 ≤ nums[i] ≤ n
All values in nums are different.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.