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