Finding the element that occurs more often than the other

I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.

Example : $aaaaaabbb$

Here $a>b$.

I have to find an constant time algorithm. Is it possible? The only thing I could come up with was using stack. Push all $a$'s and pop them with $b$. But it takes $O(n)$ operations. Any better approaches? Need a hint (no solution).

• I feel like its a very basic question, but I am not able to come up with any better ideas :(
– avi
Apr 12, 2013 at 15:31
• Just a note if your array was not sorted. Go through the array and maintain a counter. For every $a$, increment the counter and for every $b$ decrement it. In the end, you have computed $|a|-|b|$. Its sign tells you the winner. This is basically what you suggested, but without the stack :-) Shaull's answer is good for what you actually ask.
– Juho
Apr 12, 2013 at 15:58
• +1. even better without any extra space. Thanks for the idea :)
– avi
Apr 12, 2013 at 17:14

If the middle number is $a$, then since the array is sorted, $a$ appears more than $b$, and otherwise $b$ does.
This is impossible in a standard TM, and even in a RAM model. It requires at least $O(\log n)$ operations in the latter, where $n$ is the length of the array.