Find The Missing Number

Computer Science Level 3

You are given a list/array of n − 1 n-1 unsorted positive integers which you know to be the first n n whole numbers with one of them missing.

About how many operations are needed (as a minimum) to determine which number is missing?

Note: For the purposes of this problem, one operation is defined as an addition, subtraction, multiplication, division, or element comparison.

Just for fun : Can you use your algorithm to find the missing number in this list of 9999 of the first 10,000 whole numbers?

n log ⁡ n n\log n n n n \sqrt n n 2 n^2

View wiki
Clara Blackstone by Clara Blackstone , 32, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Eli Ross Staff
Feb 3, 2016

We can find the sum of all of the numbers in the list in about n n operations. Simply subtract this from 1 + 2 + 3 + … + n = n ( n + 1 ) 2 1+2+3+\ldots+n = \frac{n(n+1)}{2} and we've found the missing number!

For the data set given, the missing number is 1337. 1337.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...