### Software Job - Interview Question

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 &nbsp; -- Formula : n (n+1)/2.

The result of subtraction is the answer for this question.
``````

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

1. good one :)

1. Tks very much for your post.

Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

You also find all interview questions at link at the end of this post.

Best rgs

2. Better than sort one, but inferior to yours sum of series.

Create one more boolean array of length 52.
Iterate over first array, for each number encountered mark its position in second array as true i.e., if you encounter 4 mark 4th element in second array as true.

Finally iterate over second array and find which one is false.
So just 2 iterations overall, but memory consumption is more.

1. The solution you proposed is almost the same as 'sorting and looping through'.

After I wrote this post, I created an alternative solution using 'bitset' operator. This logic is useful not just for 1 missing number (as in the above logic), but also for multiple missing numbers. Here's the link: http://java-bytes.blogspot.com/2012/02/missing-number.html

3. Thanks for the article, excellent stuff.
I have seen interesting Interview Questions and Answers here.

4. Thank you for this post.its very informative...
Yatiken Software

5. Its very beneficial blog. this is very useful for everyone. Want a more latest job vacancies update. Visit Here

6. Tks very much for your post.

Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

You also find all interview questions at link at the end of this post.