Best algorithm to find the duplicate number

Hi All,

This is an interview question faced by my friend and hence posting here looking for some best answers.

There are 100 numbers out of which one number has a duplicate while all other numbers are unique.
What is the best algorithm to find the duplicate number.
Having a for loop/iterating is really a school kids work.
Need some good way out.

I coud think of only quick sort algorithm, as in the process of sorting we can find the duplicate also (checking for the equal value).
Any good suggestions please...!!!

Regards,
Sriram

Hi Sriram,

I think when we talk about efficiency we need to consider Space-time tradeoff.

So I think in this case if time is your criteria and not the space, then sorting the entire array is not a good idea, alternative can be using HashSet. add() and check the returned boolean value, if its false the value that you are adding already exists in the set hence its a duplicate number, Time wise it be more efficient then sorting the entire array but consume more memory space.

Regards
Tarun