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.
  • Through this contest, selected students get access to a free 6 month LinkedIn Premium subscription which helps students:
    • 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.

SOLUTION

Click here

Xor Palindrome solution codechef is one of the most asked coding question. This question is repeated in almost every company paper and if you are ready to crack the interviews and the question papers then you must check our website on daily purpose so that you can get the answer of the latest question “Xor Palindrome solution codechef”.

Leave a Comment