If you want to make money online : Register now

# [Solved]: Finding the element that occurs more often than the other

, ,
Problem Detail:

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 am guessing that the solution you are meant to give is to check the middle entry in the array. Below is a spoiler as to why this works. Hover with mouse to see, but I suggest you try to figure it out alone first.

If the middle number is \$a\$, then since the array is sorted, \$a\$ appears more than \$b\$, and otherwise \$b\$ does.

However, it is not really true that this is a constant time algorithm, as it assumes you can compute the length of the array in constant time.

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.