1
\$\begingroup\$

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 \le i\$, \$j \le N\$)
  • Change \$A_i\$ and \$A_j\$ to \$Ai \oplus Aj\$​. Here \$\oplus\$ represents the bitwise XOR operation.

Input

A binary string consisting of 0's and 1's

Output

The minimum number of operations required to make the binary string a palindrome

Reference

Here's the link of the problem.

Actual Doubt

I tried solving it by the logic that the number of operations required would be equal to the number of inequalities of characters in the string when traversing from left and right. simultaneously.

My code:

for(int i=0,j=n-1;i<n/2;i++,j--) {
    if(b[i]!=b[j]) count++;
 }

Where b is the binary string and n is it's length.

But, it turns out the solution is this:

for(int i=0,j=n-1;i<n/2;i++,j--) {
    if(b[i]!=b[j]) count++;
  }
  
cout<<(count+1)/2<<endl;

And I don't understand why.

Can someone explain this? Thanks.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The solution is correct because if \$a\neq b\$ and \$c\neq d\$ then \$a\oplus c = b\oplus d\$ (if a,b,c,d are bits), so you can pair the values on each side. Regardless, this challenge is currently missing an objective winning criterion, and is thus off-topic here. I'd suggest that you change it into code-golf. \$\endgroup\$ Commented Jun 17, 2023 at 6:15
  • 2
    \$\begingroup\$ Welcome to Code Golf! Just to expand on the second part of @CommandMaster's comment, you currently have the code-challenge tag, but you haven't specified how solutions will be scored. The most common way of scoring solutions is "shortest code wins", which is code-golf, so I'd recommend removing code-challenge and adding code-golf. \$\endgroup\$
    – The Thonnu
    Commented Jun 17, 2023 at 6:31

0