I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task:

Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected running time of your algorithm should be linear.

And authors provied following hint:

Hint: determine the (n/10)-th largest key using quickselect and check if it occurs more than n/10 times.

Actually it is not cleat for me how can quick select help me. quick select is algorhitm which can help to find k-th largest element in linear time. In the lecture materials written that it work approximately linear.

Let's work with example. We have 100 elements array. We found 10-th elements. ( frankly speaking according the book we found such element order that all elements with index > 90 more or equals than elems[90] and all elements with index < 90 less or equals elem[90]

  1. How can I calculate occurences?
  2. Imagine, that we calculated occurences and it is less than 10. What would be the next step?



  • $\begingroup$ The hint seems wrong. Can you double check? $\endgroup$
    – John L.
    Dec 2, 2018 at 14:31
  • $\begingroup$ @Apass.Jack, dl4.joxi.net/drive/2018/12/02/0005/3037/338909/09/… $\endgroup$ Dec 2, 2018 at 14:34
  • $\begingroup$ Finally I can see the hint make sense! $\endgroup$
    – John L.
    Dec 3, 2018 at 16:26
  • $\begingroup$ @Apass.Jack, could you elaborate? $\endgroup$ Dec 3, 2018 at 16:50
  • $\begingroup$ Yes, I will. The basic idea is divide and conquer built on top of quickselect. $\endgroup$
    – John L.
    Dec 3, 2018 at 16:54

1 Answer 1


Perhaps the hint was aiming at the following approach. Suppose that the array were sorted. If a value appears $m$ times and we divide the array into intervals of length $m$, then the value must appear at the end of one of the intervals. This suggests the following algorithm for finding all values that appear $n/C$ times: compute the $i \cdot n/C$-largest elements for $1 \leq i \leq C$, and for each of them, check whether the value appears at least $n/C$ times. Each iteration takes $O(n)$ time using Quickselect, for a total of $O(Cn)$ time.


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.