Author: shanu_singroha
Tester: abhidot
Editorialist: iceknight1093

1604

None

# PROBLEM:

You’re given an array A. Let Z be the sum of its two largest elements.

FInd out whether there exists a rearrangement of A such that A_i + A_{i+1} \lt Z for each 1 \leq i \lt N.

# EXPLANATION:

Let M_1 and M_2 be the two largest elements of A, with M_1 \geq M_2.
It is enough to check whether there exists a rearrangement of A such that no occurrence of M_1 is adjacent to any occurrence of M_2.

There are two possible cases here: M_1 can equal M_2, or they can be different.

• Suppose M_1 = M_2; let this value be M. We want to check whether A can be rearranged such that no two occurrences of M are adjacent.
The absolute best we can do is to place instances of M at alternate positions, i.e, position 1, 3, 5, 7, \ldots
So, the best we can do is \left\lceil \frac{N}{2} \right\rceil positions.
Hence, if the count of M in A exceeds \left\lceil \frac{N}{2} \right\rceil, the answer is No. Otherwise, the answer is Yes.
• Suppose M_1 \neq M_2. Then, there is exactly one occurrence of M_1 in A, so we need to check if all the occurrences of M_2 can be placed non-adjacent to it.
Obviously, if every other element is M_2 (i.e M_2 occurs N-1 times) this is impossible.
Otherwise, it’s always possible — for example, place all the occurrences of M_2 at positions 1, 2, 3, \ldots and place M_1 at position N.
So, in this case it’s enough to check whether the count of M_2 equals N-1 or not.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
m1, m2 = a[-1], a[-2]
if m1 == m2:
print('Yes' if a.count(m1) <= (n+1)//2 else 'No')
else:
print('Yes' if a.count(m2) <= n-2 else 'No')

2 Likes

hi , what I did was
considering 2 cases →

1. maximum is repeated - if maximum is repeated-> if maximum is repeated n times
then we need (n-1) gaps are created and we need to see if we have more than n-1 elements smaller than the maximum element.

2)maximum is not repeated and 2nd maximum is repeated then for n (2nd)maximum value n+1 gaps are created and we have to check if there are atleast n+1 elements other than maximum and 2nd maximum.

my approach couldnt pass 2 test cases can u tell me where am i wrong ( give me an example:))