1
$\begingroup$

Given an array with n rational numbers, element in is array called popular if it have appeared at least in 51% of the indices.

I have to design an algorithm that finds such element in O(n) worst case complexity time, that if there is one.

The only ideas I have is to use hash tables but the complexity time is O(n) in average and counting sort but it only works with natural numbers.

Is there anything I am missing or I can use ?

Improve this question
$\endgroup$
5
  • $\begingroup$ This is a popular question which has appeared before on this site. There is a trick. $\endgroup$
    – Yuval Filmus
    Commented Mar 10, 2018 at 14:10
  • $\begingroup$ Can you reference me to the question please ? I have no idea what is the problem called, I tried to search but I couldn't find a thing. $\endgroup$
    – Arsen
    Commented Mar 10, 2018 at 14:12
  • $\begingroup$ The search facility here is abysmal. $\endgroup$
    – Yuval Filmus
    Commented Mar 10, 2018 at 14:12
  • $\begingroup$ Maybe you can give me a hint about the trick ? $\endgroup$
    – Arsen
    Commented Mar 10, 2018 at 14:14
  • $\begingroup$ Find the median. $\endgroup$
    – Yuval Filmus
    Commented Mar 10, 2018 at 14:37

2 Answers 2

Reset to default
5
$\begingroup$

If element appears more than 50% of time, you can use Median of medians algorithm by Blum et. al. It is not deterministic though.

Or use specialized algorithm by Boyer and Moore called "Majority vote algorithm". It works by keeping counters of seen element, incrementing on the same symbol and decrementing otherwise. If counter drops to zero, the next symbol is picked.

The trick is that number of increments (and decrements for other symbols) will leave the most frequent item at the end. The second pass is required, because algorithm always terminates with some symbol, which is either the most frequent symbol or some random one (if the most frequent item - the mode - occurs below 50%, there is no guarantee it will be returned).

Here is old-school animation of the majority vote algorithm at authors webpage.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The "majority vote algorithm" is pure genius for this. I thought whether it could be adapted to find elements with high frequencies, but it fails to find a 50% element in the sequence (1, 0, 2, 0, 3, 0, 4, 0, 5, 0, ...). You should be able to adapt "median of medians" to find all elements that appear more than a third of the time, more than a fourth of the time, and so on. $\endgroup$
    – gnasher729
    Commented Mar 10, 2018 at 20:26
  • 1
    $\begingroup$ If you try to find the median, you don't actually need it exactly. If you find for example that 32% of all values are ≤ X, and 20% are ≥ Y, then only X and Y can possibly have 48% or more. $\endgroup$
    – gnasher729
    Commented Mar 10, 2018 at 21:54
  • $\begingroup$ With the "majority vote algorithm", you will often get away with not counting the elements equal to X. At the end of the first pass, you know that among the last n elements, there are m elements more equal to X than elements not equal to X. So the number of elements equal to X among the last n is equal to m + (n-m)/2. That may already be enough information. $\endgroup$
    – gnasher729
    Commented Mar 10, 2018 at 23:57
  • $\begingroup$ It seems that another pass (with different start) to keep info would help to find less frequent mode. I thought about adding counters, but it starts to look like hashtable then. Yes, in many cases one may get away with it, even keeping maximum counter with element stored seen so far is extremely helpful. In fact, any simple hashtable will work with high probability very fast, but the mere idea is superior to crude histogram. $\endgroup$
    – Evil
    Commented Mar 11, 2018 at 1:45
0
$\begingroup$

step 1: find the median: O(n)
step 2: count number of occurrence of the median value, O(n)

If a number appears more than 50%, it must be the popular element.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think it duplicates my answer. Yes it will work. $\endgroup$
    – Evil
    Commented Mar 10, 2018 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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