I was looking at a question:

Q. Given n numbers of which all numbers are repeated (at least once) other than one. We have to find that number.

Numbers range is to 10^9, thus using count sort would do no good.!

Adding the numbers one by one to a dictionary was another option (and a good one as the complexity is O(n)). But this has high implementation requirements.!

Can someone suggest some better answer to this problem.? :-/