 # ARREQU - Editorial

Author: S. Manuj Nanthan
Tester: Harris Leung
Editorialist: Nishank Suresh

1281

Observation

# PROBLEM:

Chef has an array A of length N. Can it be rearranged such that no two adjacent elements are equal?

# EXPLANATION:

Let the maximum frequency of an element in A be M. Then, the answer is “Yes” if and only if M \leq \left\lceil \frac{N}{2}\right\rceil, i.e, 2\cdot M \leq N+1.

Proof
• First, suppose that some element x appears strictly more than \left\lceil \frac{N}{2}\right\rceil times. Then clearly in any rearrangement, there will be two occurrences of x next to each other.
• Next, suppose that every element appears \leq \left\lceil \frac{N}{2}\right\rceil times. A valid rearrangement can be constructed recursively as follows:
• If N = 1 or N = 2, nothing needs to be done - any array is good.
• Otherwise, let x and y be the two elements with highest frequency in A. Remove one occurrence of x and y from A, and solve it for length N-2 recursively (note that since we are removing the elements with highest frequency, the condition on maximum frequency still holds). Now, append either [x, y] or [y, x] to the solution obtained from N-2: at least one of these will not cause a conflict and we are done.

This gives us a simple solution:

• Count the frequency of every element of A using some method (map in C++, dict/collections.Counter in python, sorting, etc)
• The answer is “Yes” if the maximum frequency is \leq \left\lceil \frac{N}{2}\right\rceil and “No” otherwise.
• To be safe and not have to deal with floating-point issues, check the condition 2\cdot M \leq N+1 instead of computing \left\lceil \frac{N}{2}\right\rceil.

# TIME COMPLEXITY

\mathcal{O}(N) or \mathcal{O}(N\log N) per test case, depending on implementation.

# CODE:

Editorialist's code (Python)
import collections
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = collections.Counter(a)
print('yes' if 2*max(freq.values()) <= n+1 else 'no')