If you want to make money online : Register now

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

, , No Comments
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).

Asked By : avi

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11266

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback