Xor Palindrome Solution

Problem

You are given a binary string $A$ of length $N$.

You can perform the following type of operation on the string $A$:

• Choose two different indices $i$ and $j$ $(1\leq i,j\leq N)$;
• Change $A_i$ and $A_j$ to $A_i \oplus A_j$. Here $\oplus$ represents the bitwise XOR operation.

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

Input Format

• First line of the input contains $T$, the number of test cases. Then the test cases follow.
• First line of each test case contains an integer $N$ denoting the size of the string.
• Second line of each test case contains a binary string $A$ of length $N$ containing $0$s and $1$s only.

Output Format

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

Constraints

• $1 \leq T \leq 1000$
• $1 \leq N \leq 2 \cdot 10^5$
• Sum of $N$ over all test cases does not exceeds $2 \cdot 10^5$.

Sample 1:

Input

Output

4
5
11011
7
0111010
1
1
4
1100

0
1
0
1

Explanation:

Test Case $1$ : The given string $11011$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $2$ : The given string $0111010$ is not a palindrome.

• Choose the indices $i=3$ and $j=5$. Now, $A_3 \oplus A_5 = 1\oplus 0 = 1$. Thus, we set $A_3$ and $A_5$ equal to $1$.

After the operation, the resulting string is $0111110$ which is a palindrome. The number of operations required is $1$.

Test Case $3$ : The given string $1$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $4$ : The given string $1100$ is not a palindrome.

• Choose the indices $i=1$ and $j=2$. Now, $A_1 \oplus A_2 = 1\oplus 1 = 0$. Thus, we set $A_1$ and $A_2$ equal to $0$.

After the operation, the resulting string is $0000$ which is a palindrome. The number of operations required is $1$.

Program :

 #include <stdio.h>

int main(void) {

// your code goes here

int t;

scanf("%d",&t);

while(t--){

    int n;

    scanf("%d",&n);

    char s[n+1];

    scanf("%s",s);

    int c=0;

    for(int i=0, j=n-1; i<j; i++, j--){

        if(s[i]!=s[j])

            c++;

    }

    printf("%d\n",(c+1)/2);

}

return 0;

}