loading...
Cover image for The Gauss Sum, and Solving for the Missing Number

The Gauss Sum, and Solving for the Missing Number

alisabaj profile image Alisa Bajramovic ・3 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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.)

Numbers 1, 2, 3 on the left side in black, and 98, 99, 100 on the right side in black, with an ellipses (...) in between them. A blue arch connects 1 and 100, and above it is "1 + 100 = 101" in blue. A red arch connects 2 and 99, and above it is "2 + 99 = 101" in red. A green arch connects 3 and 98, and above it is "3 + 98 = 101" in green.

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

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)
}