Xor Palindrome || codechef solution

Rajnish Tripathi 05:30

 Problem

You are given a binary string � of length �.

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

  • Choose two different indices � and � (1≤�,�≤�);
  • Change �� and �� to ��⊕��. Here ⊕ 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 �, the number of test cases. Then the test cases follow.
  • First line of each test case contains an integer � denoting the size of the string.
  • Second line of each test case contains a binary string � of length � containing 0s and 1s only.

Output Format

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

Constraints

  • 1≤�≤1000
  • 1≤�≤2⋅105
  • Sum of � over all test cases does not exceeds 2⋅105.

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 �=3 and �=5. Now, �3⊕�5=1⊕0=1. Thus, we set �3 and �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 �=1 and �=2. Now, �1⊕�2=1⊕1=0. Thus, we set �1 and �2 equal to 0.

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

Code(c++):-

#include <iostream>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
     int n;
     cin>>n;
     string s;
     cin>>s;
     int mid=n/2,ans=0;
    
     int l=0,r=n-1;
     while(l<r)
     {
     if(s[l]!=s[r])
     ans++;
     l++,r--;
     }
    
     cout << (ans+1)/2 <<endl;
    
    }
    return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-





Tags: