The Gauss Sum, and Solving for the Missing Number

Today's algorithm is the Missing Number problem:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

So, if you were given the array [4, 1, 0, 2, 5], the function should return 3, since that's the missing number in the consecutive order.

Typically when solving algorithms, I try to approach them using methods that are very applicable to a wide range of problems. Every so often, however, I really like a solution that utilizes an established formula or algorithm, particularly if I feel that formula can be used in a number of different ways. To solve this problem, I'll be using something called the "Gauss Sum", a trick that comes in handy when solving a range of number-based algorithms.

Gauss's Sum, and How to Approach This Problem

The story behind the Gauss Sum is that there once was a child named Carl Gauss, and when he was in grade school he was asked to sum all of the numbers from 1 to 100. He quickly responded that the answer was 5050, after picking up on a pattern: summing the first and last number in the series was 101. Summing the second and second to last number in the series was 101, and so on. (You can read more about it here.)

In other words, if you want to find the sum of all of the consecutive numbers from 0 to n, you can use the formula:
sum = (n * (n + 1)) / 2

In this problem, we can find the "missing number" by finding the Gaussian Sum of the numbers, finding the actual sum of the numbers, and returning the difference.

For example, if the given array nums was [2, 0, 3], the Gaussian Sum would be (3 * (3 + 1)) / 2, which is 6. (Why did we know that n = 3? Since only one number is missing from the array, and the array starts counting at 0, we know that the largest number, n, in the array is equal to the length of the array.) The actual sum of the digits in the array is 5 (2 + 0 + 3). The difference between the Gaussian sum and the actual sum is 1, which is our missing number.

Coding the Solution

The code for this solution is actually just three lines -- but, of course, that doesn't mean it's simple. The first thing we'll do is calculate the Gaussian Sum.

function missingNumber(nums) {
  const gaussSum = (nums.length * (nums.length + 1)) / 2;
  //...
}

Now, we want to calculate the actual sum of the digits in the nums array. To do that, we can use .reduce(), a method which can find the sum total of elements in an array. There's a lot you can do with .reduce(), and you can learn more about it here, but for the purposes of this problem, we're going give it two arguments: an accumulator and a current value.

The accumulator keeps track of the sum total of values that have been seen, and is ultimately returned by the function. The current value is the current element we're on in the array. .reduce() uses the callback function that's passed into it to perform an execution on each current element. So, in this problem, we want to sum all of the elements in the array, which means that the callback function will be accumulator + currentValue.

function missingNumber(nums) {
  const gaussSum = (nums.length * (nums.length + 1)) / 2;
  const actualSum = nums.reduce((accumulator, currentValue) => accumulator + currentValue);
  //...
}

Finally, we can return the difference between gaussSum and actualSum, which is the missing number in the array.

function missingNumber(nums) {
  const gaussSum = (nums.length * (nums.length + 1)) / 2;
  const actualSum = nums.reduce((accumulator, currentValue) => accumulator + currentValue);
  return gaussSum - actualSum;
}

--
There's definitely a number of different ways this algorithm can be solved, so please let me know if you have any questions or other solutions to this problem!

Comments

[Duy K. Bui]

I have seen problems like these solved more elegantly with XOR. If the numbers are very large, and the array is very long, you will run out of memory to hold your sum value. With XOR approach, the "counter" is only ever as large as the biggest number in the input array, regardless of array length.

The foundations of XOR approach are:

1. any number, when XOR with itself, yields 0.
2. any number, when XOR with 0, yields itself.

So in the example above, we have input [4, 1, 0, 2, 5].
If we create a second array of [0, 1, 2, 3, 4, 5] and XOR everything together, we will have

4 xor 1 xor 0 xor 2 xor 5 xor 0 xor 1 xor 2 xor 3 xor 4 xor 5

which is equal to

(0 xor 0) xor (1 xor 1) xor (2 xor 2) xor 3 xor (4 xor 4) xor (5 xor 5)

which is equal to 3. That's the missing number.

In fact we do not need to create the second array of [0, 1, 2, 3, 4, 5] either because that's just consecutive numbers, we can get it easily by using a single counter variable, or just use index of the input array (which goes naturally 0, 1, 2, 3, 4, etc.).

Solution would look something like this

function missingNumber(nums) {
  return nums.reduce((accumulatedResult, currentNumber, currentIndex) => {
    return accumulatedResult ^ currentNumber ^ (currentIndex +1 )
  }, 0)
}

[Alex Jones]

I could be wrong, but I think the guass sum equation is incorrect. It should be:

const gaussSum = (nums[nums.length - 1] * (nums[nums.length - 1] + 1)) / 2`