Sum technique

1 minute read

The Problem

Leetcode 268. Missing Number: Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

The Solution

The most obvious solution is to iterate from 0 to n, and for each number, we iterate through the given array to check if the number is present. If the length of the array is m, then the complexity for this alogorithm is O(mn) or quadratic time.

A better solution is to consider sorting the array and scan through the array to find the missing number. This will definitely work but the complexity is O(nlgn).

Let’s see if we can do better. We see that:

  1. The numbers are sequence of non-negative, ordered, and increasing number.
  2. An array of length 3 will only contain any 3 of the sequence of 4 numbers, i.e. 0, 1, 2, 3).

Observation 2 implies that there will always be a missing number. Observation 1 tells us that aprat from the missing number, the array contains the other numbers in the sequence.

Since we know the full sequence, we can compute the sum of that sequence then find the difference with the sum of the array, which is basically our missing number.

def missing_number(nums):
    n = len(nums)
    sequence_sum = n*(n+1)//2
    return sequence_sum - sum(nums)

func missingNumber(nums []int) int {
    n := len(nums)
    
    sequenceSum := n*(n+1)/2
    
    arraySum := 0
    for _, n := range nums {
        arraySum += n
    }
    
    return sequenceSum - arraySum
}

The Analysis

We need to know 2 variables:

  1. The sum of the full sequence: this can be quickly in O(1) using arithmetic progression formula.
  2. The sum of the array which can only be calculated by iterate through the array in O(n)

Hence the overall complexity will be linear or O(n).

Obviously this technique only works if you know the sequence of numbers whose the given array contain with exactly 1 missing number. An interesting question is whether this technique can be modified to use the product instead of the sum, i.e. we calculate the product of the full sequence and array, then do the division to find the missing number. We can construct an example to see that the product approach does not always work.

Input: [0]
Outout: 1

Updated:

Leave a comment