Best algorithm to find the duplicate number

[Sriram Sharma]

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

[Gupta Tarun]

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