Missing Number: Solution

Problem

Missing Number

Whiteboard

whiteboard-Medium

Challenge

coding-challenge-Easier

Concepts

Runtime, General

Download

missing-number-solution.zip

Solution #1: Simple

You could keep track of the numbers you’ve seen and then check which one is missing.

def missing_number(nums, max_num):
    """Given a list of numbers 1...max_num, find which one is missing.

    *nums*: list of numbers 1..[max_num]; exactly one digit will be missing.
    *max_num*: Largest potential number in list

    >>> missing_number([1, 2, 3, 4, 5, 6, 7, 9, 10], 10)
    8
    """

    # 1st solution: Create a set and use range to check if numbers
    # in the range are in the set. 

    num_set = set(nums)
    for i in range(1, max_num + 1):
        if i not in num_set:
            return i
    return 0

Note how we’re keeping track of this—in a list with True or False for each value. This is a bit faster than, say, adding each “seen” number to a set, since we’d have do O(n) lookup for every number!

This solution is O(n) and requires additional storage.

Solution #2: Sorting

For a simple O(n log n) solution, you could sort the numbers first, then scan them to see which one is missing:

def missing_number_sort(nums, max_num):
    """Given a list of numbers 1...max_num, find which one is missing.

    *nums*: list of numbers 1..[max_num]; exactly one digit will be missing.
    *max_num*: Largest potential number in list

    >>> missing_number_sort([1, 2, 3, 4, 5, 6, 7, 9, 10], 10)
    8
    """

    # 2nd solution: if we can't create another data structure
    #               sort and scan for missing number

    nums.append(max_num + 1)
    nums.sort()
    index = 0

    for num in nums:
        if num != index + 1:
            return index + 1
        index += 1

    return 0

This solution does not require additional storage.

Solution #3: Expected Sum

For a clever-math related formula, you can just sum the numbers and subtract the sum from the expected sum—this will reveal the missing number!

def missing_number_sum(nums, max_num):
    """Given a list of numbers 1...max_num, find which one is missing.

    *nums*: list of numbers 1..[max_num]; exactly one digit will be missing.
    *max_num*: Largest potential number in list

    >>> missing_number_sum([1, 2, 3, 4, 5, 6, 7, 9, 10], 10)
    8
    """

    # 3rd solution: find missing number by comparing expected sum vs actual

    expected = sum(range(max_num + 1))

    # Alternatively, there's a math formula that finds the sum of 1..n
    # https://en.wikipedia.org/wiki/Arithmetic_progression#Sum
    #
    # expected = ( n + 1 ) * ( n / 2 )
    #

    return expected - sum(nums)

This solution is O(n) and requires no additional lists.