Find a number where it appears exactly N/2 times
algorithm, arrays
Solution
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.
Problem
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).