Algorithms Challenge - #1: Missing Number

programming
1

A list holds n distinct numbers taken from the range 0 to n, so exactly one number in that range is missing. Write missing_number(nums) that returns it.

Examples:

  • missing_number([3, 0, 1]) returns 2
  • missing_number([0, 1]) returns 2
  • missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]) returns 8
def missing_number(nums):
    """The one number from 0..n that is not in nums."""
    pass

Rules:

  • Any language or pseudocode is fine. The stub just shows the shape.
  • Say the time complexity of your approach.
  • Linear time and constant extra space

Post your solution as a reply. Answer goes up in about a day.