Xor Palindrome XORPAL Solution Codechef

Table of Contents

Codechef Xor Palindrome XORPAL Solution

A (1-indexed) binary string S of length N is called a xor palindrome if the value of Si⊕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 YES if it is possible to rearrange S to convert it into a xor palindrome. Otherwise output NO.
  • You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

Constraints

  • 1≤T≤10001≤T≤1000
  • 1≤N≤1051≤N≤105
  • SS is a binary string, i.e, contains only the characters 00 and 11
  • It is guaranteed that the sum of NN over all test cases does not exceed 2⋅1052⋅105.

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

  • Test case 1: 00 is already a xor palindrome. [The value of Si⊕S(N+1−i) is 0 for all 1≤i≤N.]
  • Test case 2: 0011 is already a xor palindrome. [The value of Si⊕S(N+1−i) is 1 for all 1≤i≤N.]
  • Test case 3: 001 can be rearranged to form 010 which is a xor palindrome. [The value of Si⊕S(N+1−i) is 0 for all 1≤i≤N.]
  • Test case 4: It can be proved that 0001 can not be rearranged to form a xor palindrome.
Xor Palindrome XORPAL Solution
Xor Palindrome XORPAL Solution

SOLUTION

Program: Xor Palindrome XORPAL Solution in Python

for _ 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")

February Long 2022 – II (Rated for Div 3)

Leave a Comment

19 − 15 =