Software Job - Interview Question

Posted on June 20, 2010

Today, I was searching for some technical articles and stumbled upon this interview question from Amazon, for which I could immediately think about some good solution. Here's the question:

We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?

I read an answer from some guy, who said to sort the numbers first and then loop through and find the number. I thought that was inefficient way of doing that. My answer is as below:

1) Calculate the sum of all numbers stored in the array of size 51

2) Subtract the sum from (52 * 53)/2   -- Formula : n * (n+1)/2

The result of subtraction is the answer for this question.

Any other solutions that you know of?!?!?!

Blog Categories
The views expressed on this blog are my personal views and do not reflect the views of my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.