# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* S. Manuj Nanthan

*Harris Leung*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1281

# PREREQUISITES:

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')
```