A Cambridge Interview Question

If I say the numbers from 1 to 100 in a random order and I miss a number, how would you determine the missing number in your head only?

Answered by a Quora user, Obinna Okechukwu:

You can obviously take the sum of all numbers and compare to 5050, but I’ll do things a little differently if I was given the challenge.

Here’s the strategy I’ll follow:

I’ll start with a count of 0. If you call out an even number, I’ll add that number to the count and if you call out an odd number, I’ll subtract the number from the count.

The nice property of this approach is that the count will ‘on average’ be small enough to fit in my head at any given instant.

Now, to get the actual number which was missing, I’ll compare the final count to 50. If it is X more than 50, then the odd number X was missing. If it is Y less than 50 then the even number Y was missing.

Advertisements
A Cambridge Interview Question

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s