I have been recently asked a question by someone and it drove me crazy as i could not give an efficient answer to a question.
so the trick is; there is an array with numbers placed from 1 to 1 million randomly but one of the integers inside the array has been duplicated and i need to find this value in the most efficient way. what could this be?
Obvious answer is to get the first value of the array and compare this with the rest and then move to the next one etc.. but this is not what is wanted, there needs to be a way to very efficiently retrieve this but how?
could you help me on this puzzle like algorithm question? thanks