Chef has an array of N integers. Chef can rearrange this array in any manner. 

Chef doesn’t like the array if any two adjacent elements are equal. Determine whether there exists a rearrangement of the array that Chef likes.

------ Input Format ------ 

- The first line will contain T - the number of test cases. Then the test cases follow.
- First line of each test case contains a single integer N - size of the array A.
- Second line of each test case contains N space-separated integers - denoting the elements of array A.

------ Output Format ------ 

For each test case, if Chef can like any rearrangement of the array print YES, otherwise print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings yes, yEs, YeS, and YES will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5
1 1 1 1 1
3
3 3 4

----- Sample Output 1 ------ 
No
Yes

----- explanation 1 ------ 
Test case $1$: There exists no rearrangement of the array which Chef will like.

Test case $2$: A rearrangement of the array that Chef likes is $[3, 4, 3]$. Note that in this rearrangement, no two adjacent elements are equal.

Source: codechef | Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	counter_arr = Counter(map(int, input().split()))
	if max(counter_arr.values()) > round(n / 2):
		print('No')
	else:
		print('Yes')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	counter_arr = Counter(map(int, input().split()))
	if n == 2:
		arr = counter_arr.keys()
		print('Yes' if arr[0] != arr[1] else 'No')
	elif max(counter_arr.values()) > round(n / 2):
		print('No')
	else:
		print('Yes')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	counter_arr = Counter(arr)
	if n == 2:
		print('Yes' if arr[0] != arr[1] else 'No')
	else:
		for value in counter_arr.values():
			if value > round(n / 2):
				print('No')
				break
		else:
			print('Yes')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	max_fre = max(d.values())
	ans = 'Yes'
	if n % 2 and max_fre > n // 2 + 1:
		ans = 'No'
	elif not n % 2 and max_fre > n // 2:
		ans = 'No'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	list = {}
	for i in l:
		list[i] = 0
	for i in l:
		list[i] += 1
	ca = 0
	if n == 2:
		if l[0] == l[1]:
			print('No')
		else:
			print('Yes')
	elif n % 2 == 0:
		for i in list:
			if list[i] > n / 2:
				print('No')
				ca = 1
				break
		if ca == 0:
			print('Yes')
	else:
		for i in list:
			if list[i] > n / 2 + 1:
				print('No')
				ca = 1
				break
		if ca == 0:
			print('Yes')


from collections import Counter
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	d = Counter(l)
	m = 0
	for i in d.elements():
		m = max(m, d[i])
	if m > (n + 1) / 2:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	for i in A:
		dic[i] = dic.get(i, 0) + 1
	lst = []
	maximum = max(dic.values())
	for i in dic.values():
		lst.append(i)
	lst.remove(maximum)
	if sum(lst) >= maximum - 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	from collections import Counter
	a = Counter(l)
	import math
	x = math.ceil(x / 2)
	for i in a.values():
		if i > x:
			print('No')
			break
	else:
		print('Yes')


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	a = {}
	for j in arr:
		a[j] = a.get(j, 0) + 1
	m = max(a.values())
	d = []
	for i in a.values():
		d.append(i)
	d.remove(m)
	if sum(d) >= m - 1:
		print('Yes')
	else:
		print('No')
t = int(input())
while t:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	d = {}
	for i in array:
		d[i] = d.get(i, 0) + 1
	m = max(d.values())
	a = []
	for i in d.values():
		a.append(i)
	a.remove(m)
	if sum(a) >= m - 1:
		print('Yes')
	else:
		print('No')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = Counter(a)
	c = list(v.values())
	m = max(c)
	c.remove(m)
	if sum(c) >= m - 1:
		print('Yes')
	else:
		print('No')


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	maxcnt = c.most_common(1)[0][1]
	if maxcnt <= len(a) - maxcnt + 1:
		print('Yes')
	else:
		print('No')


from collections import Counter
for i in range(int(input())):
	N = int(input())
	lista = list(map(int, input().split()))
	c = Counter(lista)
	k = c.most_common()
	counter = k[0][1]
	if N % 2 == 0 and counter <= N / 2 or (N % 2 == 1 and counter <= (N + 1) / 2):
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a += [-1]
	max_count = 0
	curr_count = 0
	curr_v = a[0]
	for v in a:
		if v == curr_v:
			curr_count += 1
		else:
			if curr_count > max_count:
				max_count = curr_count
			curr_count = 1
			curr_v = v
	if max_count > len(a) // 2:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	lst = list(s)
	f = {}
	flag = 0
	for i in l:
		if i not in f:
			f[i] = 1
		else:
			f[i] += 1
	for i in lst:
		if n % 2 == 0 and f[i] > n // 2:
			print('No')
			flag = 1
			break
		elif n % 2 != 0 and f[i] > (n + 1) // 2:
			print('No')
			flag = 1
			break
	if flag == 0:
		print('Yes')


def main():
	langth = int(input())
	array = [int(x) for x in input().split()]
	dish = {}
	for ile in array:
		if ile not in dish:
			dish[ile] = 1
		else:
			dish[ile] += 1
	biggest = dish[array[0]]
	for k in dish:
		if dish[k] > biggest:
			biggest = dish[k]
	if langth >= biggest * 2 - 1:
		print('Yes')
	else:
		print('No')
for t in range(int(input())):
	main()


for test in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	Max = 0
	c = 1
	for i in range(0, n - 1):
		if l[i] == l[i + 1]:
			c = c + 1
			if Max < c:
				Max = c
		else:
			c = 1
	if Max > (n + 1) // 2:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	max_freq = 0
	i = 0
	while i < n:
		j = i
		while j < n and a[j] == a[i]:
			j += 1
		max_freq = max(max_freq, j - i)
		i = j
	if max_freq <= (n + 1) // 2:
		print('Yes')
	else:
		print('No')


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	for i in l:
		dic[i] = 0
	for i in l:
		dic[i] += 1
	f = 1
	for i in l:
		if dic[i] > (len(l) + 1) // 2:
			f = 0
	if f == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	dic = {}
	for i in li:
		dic[i] = dic.get(i, 0) + 1
	x = max(dic.values())
	if n - x >= n // 2:
		print('Yes')
	else:
		print('No')


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = Counter(a)
	a = [a[item] for item in a]
	a.sort()
	k1 = a[-1]
	a.pop()
	k2 = sum(a)
	if k1 - k2 >= 2:
		print('No')
	else:
		print('Yes')


from math import ceil
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	Dick = {}
	for val in A:
		if val in Dick.keys():
			Dick[val] += 1
		else:
			Dick[val] = 1
	if max(Dick.values()) <= ceil(N / 2):
		print('Yes')
	else:
		print('No')


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for x in l:
		if x in d.keys():
			d[x] += 1
		else:
			d[x] = 1
	m = max(d.values())
	if m <= math.ceil(n / 2):
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	d = {}
	md = 0
	for num in nums:
		if num in d:
			d[num] += 1
		else:
			d[num] = 1
		md = max(d[num], md)
	if md > n - md + 1:
		print('No')
	else:
		print('Yes')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	cnt = Counter((int(i) for i in input().split()))
	if max(cnt.values()) <= (n + 1) // 2:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ss = list(set(a))
	dd = dict()
	for e in ss:
		dd[e] = 0
	for e in a:
		dd[e] += 1
	d = list(dd.values())
	d.sort()
	m1 = d[-1]
	if len(ss) >= 2:
		m2 = d[-2]
	if n == 1:
		print('Yes')
	elif m1 > (n + 1) // 2:
		print('No')
	elif len(ss) >= 2 and n % 2 == 1 and (m2 > (n - 1) // 2):
		print('No')
	else:
		print('Yes')


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	unique_dict = {}
	for j in arr:
		if j in unique_dict:
			unique_dict[j] += 1
		else:
			unique_dict[j] = 1
	if max(unique_dict.values()) > math.ceil(length / 2):
		print('No')
	else:
		print('Yes')


tc = int(input())
while tc:
	tc -= 1
	n = int(input())
	li = list(map(int, input().split()))
	dic = {k: 0 for k in li}
	for i in li:
		dic[i] += 1
	for (k, l) in dic.items():
		if 2 * l - n > 1:
			print('No')
			break
	else:
		print('Yes')


from collections import Counter
import math
T = int(input())
for _ in range(T):
	N = int(input())
	L = Counter(list(map(int, input().split())))
	for i in L.values():
		if i > math.ceil(N / 2):
			print('No')
			break
	else:
		print('Yes')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 1
	count = []
	for i in range(n - 1):
		if a[i + 1] == a[i]:
			c = c + 1
		else:
			count.append(c)
			c = 1
	count.append(c)
	if n % 2 == 0:
		if max(count) <= n / 2:
			print('Yes')
		else:
			print('No')
	elif max(count) <= (n + 1) / 2:
		print('Yes')
	else:
		print('No')


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	dict = {}
	for i in A:
		if i in dict:
			dict[i] = 1 + dict[i]
		else:
			dict[i] = 1
	max_current = 0
	for j in dict:
		if dict[j] > max_current:
			max_current = dict[j]
	if math.ceil(N / 2) >= max_current:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().strip().split()))
	d = dict()
	for i in a:
		try:
			d[i] += 1
		except:
			d[i] = 1
	maxi = d[max(d, key=lambda x: d[x])]
	if len(a) - maxi + 1 < maxi:
		print('No')
	else:
		print('Yes')
	t -= 1


n = int(input())
for i in range(n):
	n = int(input())
	A = list(map(int, input().split()))
	p = {}
	for i in A:
		if i in p:
			p[i] += 1
		else:
			p[i] = 1
	val = int(max(p.values()))
	if n - val >= val - 1:
		print('Yes')
	else:
		print('No')


import math
import collections
for i in range(int(input())):
	n = int(input())
	m = []
	l = list(map(int, input().split()))
	f = collections.Counter(l)
	f = dict(f)
	m = list(f.values())
	c = max(m)
	if c <= math.ceil(n / 2):
		print('Yes')
	else:
		print('No')