Hello I have a problem and would like a help to prove if it is P or not.

Given an array $\mathcal{A}$ of integers. Is there a permutation of the elements of $\mathcal{A}$ such that, $\forall i \in \{1, ..., |\mathcal{A}|-1\} : \mathcal{A}[i] \neq \mathcal{A}[i + 1]$?

Could anyone give me some direction on how to show if it's Polynomial or not?

  • $\begingroup$ Please do not delete your question after you have received a useful reply. We want questions and answers available in order to not only help you, but also others who have similar questions. $\endgroup$
    – Discrete lizard
    Dec 11 '20 at 11:25

Suppose for simplicity that the number $n=2k$ of elements in the array is even. Let $a$ be the (one of the) most frequent element(s) and let $m$ the number of occurrences of $a$ in $\mathcal{A}$.

A polynomial time algorithm that solves your problem is the following: return "yes" if $m \le k$, otherwise return "no".

To see this notice that if $m>k$ the answer is trivially now, since two occurrences $a$ must necessarily be adjacent in any permutation of $\mathcal{A}$.

If $m=k$ then the answer is trivially yes: just interleave the copies of $a$ with the other elements in $\mathcal{A}$.

If $m < k$, then consider the elements of $\mathcal{A}$ in nonincreasing order of their number of occurrences. Create the permutation $B$ of $\mathcal{A}$ by first filling in all odd indices and then all even indices (indices start from $1$). For each distinct element $x \in \mathcal{A}$, let $i$ be the index of the first occurrence of $x$ in $B$. If $i=1$ or $i$ is even, then no pair of elements equal to $x$ can possibly be adjacent in $B$. Suppose then that $i$ is odd and that $i>1$. In order for $B[i-1]$ to be equal to $x$, at least $k$ copies of $x$ would be needed, but at most $m \le k-1$ copies are available.


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.