Find the missing number in an array

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

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.

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

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

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.