Xor Palindrome XORPAL Solution Codechef

Codechef Xor Palindrome XORPAL Solution

A (11-indexed) binary string SS of length NN is called a xor palindrome if the value of Si⊕S(N+1−i)Si⊕S(N+1−i) is the same for all 1≤i≤N1≤i≤N.

For example, 00, 11111111 and 01010101 are xor palindromes, while 11101110 and 110101110101 are not.

You are given a binary string SS of length NN. 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 TT — the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains an integer NN — the length of the binary string SS.
  • The second line of each test case contains the binary string SS containing 00s and 11s only.

Output Format

For each test case, output YESYES if it is possible to rearrange SS to convert it into a xor palindrome. Otherwise output NONO.

You may print each character of YESYES and NONO in uppercase or lowercase (for example, yesyes, yEsyEs, YesYes 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 11: 0000 is already a xor palindrome. [The value of Si⊕S(N+1−i)Si⊕S(N+1−i) is 00 for all 1≤i≤N1≤i≤N.]

Test case 22: 00110011 is already a xor palindrome. [The value of Si⊕S(N+1−i)Si⊕S(N+1−i) is 11 for all 1≤i≤N1≤i≤N.]

Test case 33: 001001 can be rearranged to form 010010 which is a xor palindrome. [The value of Si⊕S(N+1−i)Si⊕S(N+1−i) is 00 for all 1≤i≤N1≤i≤N.]

Test case 44: It can be proved that 00010001 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

3 × three =