2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 13 '16 at 20:08
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, there might be only 1 popular number value, so it will be at least, and maybe at most, in one index only. So how can I prove it that way? Your approach is working if we have exactly 3 popular numbers. $\endgroup$ – iTayb Dec 13 '16 at 20:32
  • 1
    $\begingroup$ That's right, I misread the question. Fortunately, the changes to the argument are not dramatic. $\endgroup$ – Yuval Filmus Dec 13 '16 at 20:35

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.