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

The result of subtraction is the answer for this question.

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

4 comments:

  1. 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.

    ReplyDelete
    Replies
    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

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

    ReplyDelete