# Xor Palindrome solution codechef

## Xor Palindrome solution codechef

You are given a binary string AA of length NN.

You can perform the following type of operation on the string AA:

• Choose two different indices ii and jj (1i,jN)(1≤i,j≤N);
• Change AiAi and AjAj to AiAjAi⊕Aj. Here  represents the bitwise XOR operation.

Find the minimum number of operations required to convert the given string into a palindrome.

## Xor Palindrome solution codechef

### Input Format

• First line of the input contains TT, the number of test cases. Then the test cases follow.
• First line of each test case contains an integer NN denoting the size of the string.
• Second line of each test case contains a binary string AA of length NN containing 00s and 11s only.

### Output Format

For each test case, print the minimum number of operations required to make the string a palindrome.

## Xor Palindrome solution codechef

• 1T10001≤T≤1000
• 1N21051≤N≤2⋅105
• Sum of NN over all test cases does not exceeds 21052⋅105.
• Discover & apply to 20M+ jobs/internships on LinkedIn
• Reach out to hiring managers/recruiters/mentors directly
• Find career paths that people similar to them have taken
• Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

### Sample Input 1

2
5
11011
7
0111010


### Sample Output 1

0
1


## Xor Palindrome solution codechef

Test Case 11 : The given string 1101111011 is already a palindrome. So, no operation is required. The answer for the case is 00.

Test Case 22 : The given string 01110100111010 is not a palindrome.

• Choose the indices i=3i=3 and j=5j=5. Now, A3A5=10=1A3⊕A5=1⊕0=1. Thus, we set A3A3 and A5A5 equal to 11.

After the operation, the resulting string is 01111100111110 which is a palindrome. The number of operations required is 11.