1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I feel like its a very basic question, but I am not able to come up with any better ideas :( $\endgroup$ – avi Apr 12 '13 at 15:31
  • 3
    $\begingroup$ 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. $\endgroup$ – Juho Apr 12 '13 at 15:58
  • $\begingroup$ +1. even better without any extra space. Thanks for the idea :) $\endgroup$ – avi Apr 12 '13 at 17:14
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Figured out as soon as I read the first sentence. It was fun. Wish I had come with up the solution on my own. Thank you ! $\endgroup$ – avi Apr 12 '13 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.