You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?
Expected time complexity : O(n)
Expected space complexity : O(1)
What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)
Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html