# How to find indexes of numbers that has many occurrences?

Disclaimer: This is a simplified part of a question from my homework, addressing the point that I didn't figure out.

let A be a 1-indexed sorted array of $n$ elements.

There are at most 3 numbers that has at least $\lfloor n/4 \rfloor+1$ occurrences.

Find three indexes that will surely "hit" all such numbers. Explain why it's certain.

Because this is a sorted array, all such numbers will be stacked together, so each "number group" have a limited freedom to travel around the array.

It feels like going symmetrically for $n/4$, $n/2$ and $3n/4$ would be a wise guess, but I'm not sure how to prove it, and furthermore $n$ might not be a multiplicity of 4, so we have to round up or down the indexes.

How can I tackle such question?

• You seem to have the right idea – now it just remains to prove that it works. You can start with the case of $n$ divisible by 4. Don't give up so quickly. – Yuval Filmus Dec 13 '16 at 20:08

Let's assume for simplicity that $n$ is divisible by $4$. Aiming for a contradiction, suppose that there is some popular number (a number is popular if it appears at least $n/4+1$ times) which does not appear at any of the positions $n/4,n/2,3n/4$. Denote this popular number by $x$.
Can $x$ appear before position $n/4$? between positions $n/4$ and $n/2$? between positions $n/2$ and $3n/4$? after position $3n/4$?
If the answer to all of these questions is no, then we have reached a contradiction, and the only way out is that $x$ appears in one of the positions $n/4,n/2,3n/4$.