Computer science job interview question:

Find the missing number in the series.

Write a program to calculate the missing number in the series of integers.

There are multiple ways to do this bu

using the Gauss Sum addition method is a nice trick and it’s faster than any brute-force iteration you might think of.

More info https://en.wikipedia.org/wiki/Gauss_sum

The idea is that you take the count of elements you have including the missing number and add 1 to that then divide it by 2. This is a nice way to write some leetcode or leet-code 1337 and pretend you know what you’re doing.

https://en.wikipedia.org/wiki/Leet

The set of numbers doesn’t need to be sorted.

you can actually count the elements and add the missing array element.

Set1= 1,2,4,5,6,7,8,9,10 n * (n+1) /2

Gauss sum works like this:

Set1= 1,2,3,4,5,6,7,8,9,10

Add reversed set to itself:

Set1= 1,2,3,4,5,6,7,8,9,10 Set2= 10,9,8,7,6,5,4,3,2,1 Set= 1+10=11, 2+9=11, 3+8=11....10+1=11 Becomes 10(11)/2 =110/2 =55

This finds the Gauss sum of a whole set just by counting the items.

Then you make an actual sum of the numbers you have.

Count elements and add +1 for the missing number. SetCount = Count+9 = 9+1 = 10 Sum(Set1) = (1+2+4+5+6+7+8+9+10)=52

Now you subtract the actual sum from the Gauss sum to get the missing number.

MissingNumber = GaussSum - Sum(Set1)

Whole program steps

set1 = [1,2,4,5,6] n = count(set1) + 1 gauss_sum = n(n+1)/2 actual_sum = sum(set1) missing_number = gauss_sum - actual_sum

In the video you will see why you need to add the +1 there and why this works.

## Leave a Reply