Find Missing Number Algorithm in JavaScript

The algorithm for Day 2 of 30 Days of Algorithms is a useful formula to find a missing number in an array of numbers from 1 - N. This algorithm only works if there is one-and-only-one missing number, and no duplicate numbers. There are other algorithms for those cases which I will cover on a different day.

Given that :

a is a list of positive integers from 1 - N

a contains all unique numbers

a has one-and-only-one missing number

n == a.length

The formula for this algorithm is both simple and quite elegant. We start by finding the sum of all of the numbers in the list - sum(a) - (i.e., a[0] + a[1] + a[2], ..., a[n]).

Next, we apply the simple formula : (n + 1) * (n + 2) / 2 - sum

If you are not a fan of math, it might look daunting but it really isn't. We already know what n is - the length of the list - so we can simply replace n with its value.

Do the Math

Let's use the example case of a = [1, 2, 3, 5, 6]

There are 5 numbers in our list, a, so we merely replace n in the formula with 5.

(n + 1) * (n + 2) / 2 - sum = (5 + 1) * (5 + 2) / 2 - sum

We can simplify the formula by performing the calculations we can complete so far. So we get:

((n + 1) * (n + 2)) / 2 - (sum(5 + 1) * (5 + 2)) / 2 - (sum(6) * 7) / 2 - sum;
42 / 2 - sum;
21 - sum;

At this point, the only missing variable is sum, which we get by adding the numbers in the list. Since this is a simple case we can do that quite easily : 1 + 2 + 3 + 5 + 6 = 17

Next, we simply perform the final calculation:

21 - 17 = 4, which we can verify is the missing number.

But Why Does it Work?

There really isn't any magic going on here, we are just using the natural properties of the numbers 1 - N.

In the first step, when we add (n + 1), we are calculating how long the list would be without the missing number. Next, we calculate what the sum maximum sum could be if no numbers were missing.

It is a property of the numbers 1 - N that the highest number in the list, multiplied by the next number after the list, is twice the sum of the numbers 1 - N. For instance, if we start with the list of number from 1 - 8, the highest number is 8. So 8 * (8 + 1) = 72. If we divide 72 by 2 we get 36, which is the sum of 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8.

Once we have determined the what the sum would be for the list without any numbers missing, finding the missing number is very simple. We just subtract the sum of the actual numbers in the list.

The JavaScript Code

/**
 * Finds the missing number in a list of numbers.
 * @param   {array}   a   An array of positive integers.
 * @param   {int}     n   The length of `a`
 * @returns {number}
 * @see https://www.geeksforgeeks.org/find-the-missing-number/
 */
const findMissingNumber1toN = (a, n) => {
  /*
   * Calculate the sum of all numbers in the array.
   */
  let sum = a.reduce((a, v) => a + v);

  /*
   * Now calculate the maximum sum the array /could/
   * have with the missing number included then subtract
   * the original sum. The result is the missing number.
   */
  return ((n + 1) * (n + 2)) / 2 - sum;
};

const a = [1, 2, 3, 5, 6];

const missingNumber = findMissingNumber1toN(a, a.length);

console.log(
  "Inputs : [" + a.join(", ") + "] \n" + "Missing number : " + missingNumber
);

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.