mycsmajor
Data structures problem 4 of 30

The missing number

  • Data structures
  • Easy

A list contains n distinct numbers taken from the range 0 to n, so exactly one number in that range is missing. Find it in O(n) time and O(1) extra space.

missing([3, 0, 1])        # 2
missing([0, 1])           # 2
missing([9,6,4,2,3,5,7,0,1])  # 8
Show hint

You know what 0 + 1 + ... + n adds up to without looking at the list.

Show solution 
def missing(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

The full range sums to n(n+1)/2. Subtract what is actually there and the difference is the missing number. Another way: XOR every index and value together, and the pairs cancel out, leaving the missing number.

Want a problem like this every day? See today's problem and keep a streak going.