# algorithm to find all values that occur more than n/10 times

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?

P.S.

• The hint seems wrong. Can you double check? – John L. Dec 2 '18 at 14:31
• – gstackoverflow Dec 2 '18 at 14:34
• Finally I can see the hint make sense! – John L. Dec 3 '18 at 16:26
• @Apass.Jack, could you elaborate? – gstackoverflow Dec 3 '18 at 16:50
• Yes, I will. The basic idea is divide and conquer built on top of quickselect. – John L. Dec 3 '18 at 16:54

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.