A (1-indexed) binary string S of length N is called a *xor palindrome* if the value of S_{i} \oplus S_{(N + 1 - i)} is the same for all 1 ≤ i ≤ N.

For example, 0, 1111 and 0101 are xor palindromes, while 1110 and 110101 are not.

You are given a binary string S of length N. Determine if it is possible to rearrange it to form a xor palindrome or not.

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

- The first line of input contains a single integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N — the length of the binary string S.
- The second line of each test case contains the binary string S containing 0s and 1s only.

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

For each test case, output \texttt{YES} if it is possible to rearrange S to convert it into a xor palindrome. Otherwise output \texttt{NO}.

You may print each character of \texttt{YES} and \texttt{NO} in uppercase or lowercase (for example, \texttt{yes}, \texttt{yEs}, \texttt{Yes} will be considered identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$S$ is a binary string, i.e, contains only the characters $0$ and $1$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
2
00
4
0011
3
001
4
0001

----- Sample Output 1 ------ 
YES
YES
YES
NO

----- explanation 1 ------ 
Test case $1$: $\texttt{00}$ is already a xor palindrome. [The value of $S_{i} \oplus S_{(N + 1 - i)}$ is $0$ for all $1 ≤ i ≤ N$.]

Test case $2$: $\texttt{0011}$ is already a xor palindrome. [The value of $S_{i} \oplus S_{(N + 1 - i)}$ is $1$ for all $1 ≤ i ≤ N$.]

Test case $3$: $\texttt{001}$ can be rearranged to form $\texttt{010}$ which is a xor palindrome. [The value of $S_{i} \oplus S_{(N + 1 - i)}$ is $0$ for all $1 ≤ i ≤ N$.]

Test case $4$: It can be proved that $\texttt{0001}$ can not be rearranged to form a xor palindrome.

Difficulty: EASY
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
for pp in range(int(input())):
	rr = int(input())
	qq = input()
	zs = 0
	os = 0
	for priya in range(rr):
		if qq[priya] == '0':
			zs = zs + 1
		else:
			os = os + 1
	if rr % 2 == 0:
		if zs % 2 == 0 and os % 2 == 0:
			print('YES')
		elif zs == os:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	if n % 2 == 0:
		s0 = s.count('0')
		s1 = s.count('1')
		if s0 % 2 == 0 and s1 % 2 == 0 or (s0 % 2 != 0 and s1 % 2 != 0 and (s0 == s1)):
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 'NO'
	if s.count('1') == s.count('0') or s.count('0') % 2 == 0 or s.count('1') % 2 == 0:
		ans = 'YES'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	m1 = s.count('1')
	m2 = s.count('0')
	if n % 2 == 0:
		if m1 == m2 or m1 == n or m2 == n:
			print('YES')
		elif m1 % 2 == 0 and m2 % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for tc in range(int(input())):
	n = int(input())
	s = input()
	y = s.count('1')
	z = s.count('0')
	ans = 'NO'
	if n % 2 == 0:
		if y % 2 != 0 and z % 2 != 0 and (y == z):
			ans = 'YES'
		elif y % 2 != 0 and z % 2 != 0:
			ans = 'NO'
		else:
			ans = 'YES'
	else:
		ans = 'YES'
	print(ans)


t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeroes = s.count('0')
	flag = 0
	if n % 2 == 0:
		if ones % 2 == 1 or zeroes % 2 == 1:
			if ones == zeroes:
				flag = 1
		else:
			flag = 1
	else:
		flag = 1
	if flag == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = input()
	(c0, c1) = (l.count('0'), l.count('1'))
	if n % 2 == 0:
		if c0 % 2 or c1 % 2:
			if c0 == c1:
				print('YES')
			else:
				print('NO')
		else:
			print('YES')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	in_str = input()
	n0 = in_str.count('0')
	n1 = in_str.count('1')
	res = 'YES'
	if n % 2 == 0:
		if n0 % 2 or n1 % 2:
			if n0 == n1:
				res = 'YES'
			else:
				res = 'NO'
		else:
			res = 'YES'
	else:
		res = 'YES'
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = input()
	p = a.count('0')
	q = a.count('1')
	if n % 2 == 0:
		if p >= 1 and q >= 1 and (p == q):
			print('YES')
		elif p % 2 == 0 and q % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	if n & 1:
		print('YES')
		continue
	occ = Counter(s)
	if occ['1'] % 2 == 0 or occ['1'] == n // 2 or n == 2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if len(s) % 2 != 0:
		print('YES')
	elif len(s) == 2:
		print('YES')
	elif s.count('1') % 2 == 0:
		print('YES')
	elif s.count('1') == n // 2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n % 2 != 0:
		print('YES')
	elif n % 2 == 0:
		count0 = 0
		count1 = 0
		for i in s:
			if i == '1':
				count1 += 1
			else:
				count0 += 1
		if count0 == n or count1 == n:
			print('YES')
		elif count0 == count1:
			print('YES')
		elif count0 % 2 == 0 and count1 % 2 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	if n % 2 == 0:
		if s.count('1') == s.count('0'):
			print('YES')
		elif s.count('1') % 2 == 0 and s.count('0') % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	xor_S = 0
	count_0 = 0
	count_1 = 0
	for i in range(N):
		if S[i] == '1':
			count_1 += 1
		else:
			count_0 += 1
	if N % 2 == 0:
		if count_0 == count_1:
			print('YES')
		elif count_0 % 2 == 0 and count_1 % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	o = s.count('0')
	e = s.count('1')
	if n % 2 == 0:
		if o == e or o == n or o == e:
			print('YES')
		elif o % 2 == 0 and e % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if n % 2 == 0:
		if one == zero:
			print('YES')
		elif one % 2 == 0 and zero % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	t = int(input())
	m = 0
	n = 0
	s = input()
	for i in range(t):
		if s[i] == '0':
			m += 1
		else:
			n += 1
	if t % 2 == 0:
		if m == n:
			print('YES')
		elif m % 2 == 0 and n % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s_0 = s_1 = 0
	for i in s:
		if i == '0':
			s_0 += 1
		else:
			s_1 += 1
	if n % 2 == 0:
		if s_0 == s_1 or (s_0 % 2 == 0 and s_1 % 2 == 0):
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	o = s.count('1')
	z = s.count('0')
	if o == 0 or z == 0:
		print('YES')
	elif l & 1:
		print('YES')
	elif l % 2 == 0 and (z == o or o % 2 == 0):
		print('YES')
	else:
		print('NO')


tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	zeroes = string.count('0')
	ones = string.count('1')
	ans = 'YES'
	if ones == 0 or zeroes == 0:
		ans = 'YES'
	elif length & 1:
		ans = 'YES'
	elif length % 2 == 0 and (zeroes == ones or ones % 2 == 0):
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	on = s.count('1')
	ze = s.count('0')
	if n % 2 != 0:
		print('YES')
	elif on * ze % 2 == 0 or on == ze:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	zc = s.count('0')
	oc = s.count('1')
	if len(s) % 2 == 0:
		if zc == oc or (zc % 2 == 0 and oc % 2 == 0):
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	(a, b) = (s.count('0'), s.count('1'))
	if a == b:
		print('YES')
	elif a % 2 == 1 and b % 2 == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	c = int(input())
	d = input()
	if c % 2 == 0:
		if d.count('1') == d.count('0') or (d.count('1') % 2 == 0 and d.count('0') % 2 == 0) or (d.count('1') == c // 2 and d.count('0') == c // 2):
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	s = input()
	one = s.count('1')
	zer = s.count('0')
	if n % 2 == 0:
		if one == 0 or zer == 0:
			print('YES')
		elif one % 2 == 0 and zer % 2 == 0:
			print('YES')
		elif one == n // 2 and zer == n // 2:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def solve(s, n):
	if s.count('1') == s.count('0'):
		return True
	elif s.count('1') % 2 != 0 and s.count('0') % 2 != 0:
		return False
	return True
t = int(input())
while t:
	n = int(input())
	s = input()
	print('YES') if solve(s, n) else print('NO')
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = input()
	c0 = l.count('0')
	c1 = l.count('1')
	if n % 2 == 0:
		if c0 % 2 == 0 and c1 % 2 == 0 or ((c0 % 2 != 0 and c1 % 2 != 0) and c1 == c0):
			print('YES')
		else:
			print('NO')
	elif c0 % 2 == 0 and c1 % 2 != 0 or (c0 % 2 != 0 and c1 % 2 == 0):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = input()
	o = 0
	z = 0
	o = l.count('1')
	z = l.count('0')
	if n % 2 == 0 and o % 2 == 1 and (o != z):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	y = int(input())
	(a, q) = (0, 0)
	s = input()
	for i in range(y):
		if s[i] == '0':
			a += 1
		else:
			q += 1
	if y % 2 == 0:
		if a == q:
			print('YES')
		elif a % 2 == 0 and q % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	N = int(input())
	S = input()
	d1 = {'1': 0, '0': 0}
	for i in S:
		d1[i] += 1
	if d1['0'] % 2 == 0 and d1['1'] % 2 == 0:
		print('YES')
	elif d1['0'] % 2 ^ d1['1'] % 2:
		print('YES')
	elif d1['0'] == d1['1']:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	sum = 0
	for nm in range(N):
		sum += int(S[nm])
	if sum == 0:
		print('YES')
	elif sum == N:
		print('YES')
	elif sum % 2 == 0 and (N - sum) % 2 == 0:
		print('YES')
	elif N % 2 == 0 and sum == N - sum:
		print('YES')
	elif N % 2 != 0:
		if abs(N - 2 * sum) % 2 == 1:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	s = input()
	one = 0
	zero = 0
	for i in range(N):
		if s[i] == '0':
			zero += 1
		else:
			one += 1
	if N % 2 == 0:
		if zero % 2 == 0 and one % 2 == 0:
			print('YES')
		elif zero == one:
			print('YES')
		else:
			print('NO')
	elif zero % 2 == 0 or one % 2 == 0:
		print('YES')
	else:
		print('NO')


for m in range(int(input())):
	n = int(input())
	x = 0
	y = 0
	s = input()
	for i in range(n):
		if s[i] == '0':
			x += 1
		else:
			y += 1
	if n % 2 == 0:
		if x == y:
			print('YES')
		elif x % 2 == 0 and y % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	s = input()
	count_0 = s.count('0')
	count_1 = n - count_0
	if n % 2 == 1:
		if count_0 % 2 == 0 or count_1 % 2 == 0:
			print('YES')
			continue
	elif count_0 % 2 == 0 and count_1 % 2 == 0:
		print('YES')
		continue
	paired = min(count_0, count_1)
	count_0 = count_0 - paired
	count_1 = count_1 - paired
	if n % 2 == 1:
		if count_0 == 1 or count_1 == 1:
			print('YES')
			continue
	elif count_0 == count_1 == 0:
		print('YES')
		continue
	print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = str(input())
	(C0, C1) = (0, 0)
	for l in S:
		if l == '0':
			C0 += 1
		else:
			C1 += 1
	if N % 2 == 0:
		if C0 % 2 == 0 and C1 % 2 == 0:
			print('YES')
		elif C0 == C1:
			print('YES')
		else:
			print('NO')
	elif abs(C0 - C1) % 2 == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	S = str(input())
	(A, B) = (S.count('0'), S.count('1'))
	if N % 2 == 0:
		if A == B:
			print('YES')
		elif A % 2 == 0 and B % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def my_func(n, s, l, k):
	for i in range(n):
		if s[i] == '0':
			k += 1
		else:
			l += 1
	if n % 2 == 0:
		if k == l:
			print('YES')
		elif k % 2 == 0 and l % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
for _ in range(int(input())):
	n = int(input())
	(l, k) = (0, 0)
	s = input()
	my_func(n, s, l, k)


for k in range(int(input())):
	n = int(input())
	a = 0
	b = 0
	s = input()
	for i in range(n):
		if s[i] == '0':
			a += 1
		else:
			b += 1
	if n % 2 == 0:
		if a == b:
			print('YES')
		elif a % 2 == 0 and b % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def XOR(s, n):
	if len(s) == 0:
		return 'NO'
	ones = s.count('1')
	zeros = len(s) - ones
	if ones == n or ones == 0:
		return 'YES'
	elif ones == zeros:
		return 'YES'
	elif n == len(s):
		if ones % 2 == 0 or zeros % 2 == 0:
			return 'YES'
		else:
			return 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	result = XOR(s, n)
	print(result)


t = int(input())
for i in range(t):
	N = int(input())
	S = input()
	C_1 = 0
	C_0 = 0
	for i in S:
		if i == '1':
			C_1 += 1
		else:
			C_0 += 1
	if N % 2 == 0:
		if N == C_0 or N == C_1:
			print('YES')
		elif C_1 == C_0:
			print('YES')
		elif C_0 % 2 == 0 and C_1 % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = int(input())
	b = input()
	l = []
	for j in b:
		c = int(j)
		l.append(c)
	s = 0
	for k in l:
		s = s + k
	if a % 2 == 0:
		if s % 2 == 0:
			print('YES')
		elif s == a // 2:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def check(binary):
	ones = binary.count('1')
	twos = binary.count('0')
	if len(binary) == 1:
		return True
	if ones == twos:
		return True
	if ones % 2 == 0 or twos % 2 == 0:
		return True
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	binary = input()
	result = check(binary)
	if result:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	if n % 2 != 0:
		print('YES')
	else:
		a = s.count('1')
		b = s.count('0')
		if a % 2 == 0 and b % 2 == 0 or a == b:
			print('YES')
		else:
			print('NO')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	count0 = s.count('0')
	count1 = n - count0
	if n % 2 == 1 or count1 == count0 or (count1 % 2 == 0 and count0 % 2 == 0):
		print('YES')
	else:
		print('NO')