Find a number where it appears exactly N/2 times

Question

Here is one of my interview question. Given an array of N elements and where an element appears exactly N/2 times and the rest N/2 elements are unique. How would you find the element with a better run time?

Remember the elements are not sorted and you can assume N is even. For example,

input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 } 

So here 10 appears extactly 5 times which is N/2.

I know a solution with O(n) run time. But still looking forward to know a better solution with O(log n).

Answer 1

There is a constant time solution if you are ready to accept a small probability of error. Randomly samples two values from the array, if they are the same, you found the value you were looking for. At each step, you have a 0.75 probability of not finishing. And because for every epsilon, there exists one n such that (3/4)^n < eps, we can sample at most n time and return an error if we did not found a matching pair.

Also remark that, if we keep sampling until we found a pair, the expected running time is constant, but the worst case running time is not bounded.

Answer 2

Here is my attempt at a proof of why this cannot be done in less than O(n) array accesses (for worst case, which surely is the only interesting case in this example):

Assume a worst case log(n) algorithm exists. This algorithm accesses the array at most log(n) times. Since it can make no assumptions about which elements are where, let me choose which log(n) elements it sees. I will choose to give it the first log(n) unique elements. It has not found the duplicate yet, and there still exist n/2 - log(n) unique elements for me to feed it if need be. In fact, I cannot be forced to feed it a duplicated number until it has read n/2 elements. Therefore such an algorithm cannot exist.

From a purely intuitive standpoint, this just seems impossible. Log(4 billion) is 32. So with an array of 4 billion numbers, 2 billion of which are unique, in no particular order, there is a way to find the duplicated element by only checking 32 elements?