```
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?!?!?!

good one :)

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

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

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

DeleteAfter 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

Thanks for the article, excellent stuff.

ReplyDeleteI have seen interesting Interview Questions and Answers here.