# FLIPPAL - Editorial

Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh

1173

None

# PROBLEM:

Given a binary string S, in one move you can pick two indices and flip their values. Is it possible to make the final string a palindrome?

# EXPLANATION:

You might notice that performing an operation on two indices with two different values essentially swaps the values at these indices. This is already enough to make S into a palindrome whenever:

• N is odd; or
• N is even and contains both an even number of 0's and 1's
Proof

When N is even, for S to be a palindrome both the 0's and the 1's must occur an even number of times, since each 0/1 is paired with another 0/1.

Itâ€™s fairly easy to see that if this condition holds, then just swapping 0's with 1's can make S into a palindrome. For example, if there are x occurrences of 0 and y of 1, then make the first x/2 and last x/2 characters of S 0 using swaps. This is a palindrome.

Further, any odd-length string can always be made a palindrome.
Either the 0's or the 1's must occur an odd number of times in an odd-length string; suppose itâ€™s the 0's.
Use one swap to make a 0 the middle character. Now, the remaining part of the string needs to be an even palindrome, and we satisfy the condition above so weâ€™re done.

As it turns out, these conditions are both necessary and sufficient.

Proof

Note that the given operation doesnâ€™t actually change the parities of the 0's and 1's.
Let c_0 and c_1 be the respective counts. Then, one operation can change them as follows:

• c_0 \to c_0 + 2 and c_1 \to c_1 - 2 (flipping two 1's to 0)
• c_0 \to c_0 - 2 and c_1 \to c_1 + 2 (flipping two 0's to 1)
• Leave c_0 and c_1 unchanged (swapping a 0 and a 1)

All three cases donâ€™t change the parities. However, our earlier conditions only depended on the parities of c_0 and c_1. So, those cases are both necessary and sufficient.

Thus, the final solution is as follows: compute c_0 and c_1, the counts of 0 and 1 in the string. Then,

• If both c_0 and c_1 are odd, the answer is â€śNoâ€ť.
• Otherwise, the answer is â€śYesâ€ť.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
z, o = s.count('0'), s.count('1')
if z%2 == 1 and o%2 == 1:
print('NO')
else:
print('YES')

1 Like

Can anyone tell me what mistake I made in the code pasted below:

#include <iostream>
using namespace std;

int main() {
int t;
cin >> t;
while(t--){
int n;
string s;
cin >> n >> s;
if(n == 2 && s[0] != s[1])   cout << "NO" << endl;
else    cout << "YES" << endl;
}
return 0;
}


You need to count number of swaps necessary for making the string a palindrome if n is even.
If the count is even then answer is yes else it is no.
I think you can try proving that yourself why it works.
However if n is odd, it is always possible to make the string a palindrome

1 Like

Can anyone tell me what mistake I made in this code ?

#include <bits/stdc++.h>
using namespace std;
int main()
{

int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
char a[n];

long long int i, c1 = 0, c0 = 0;

cin >> a;

for (i = 0; i < n; i++)
(a[i] == '1') ? (c1++) : (c0++);

// cout<<c1<<" "<<c0<<endl;

if((c1%2==0 && c0%2==0)||(c1%2==0 && c0%2==1)||(c1%2==1 && c0%2==0))
cout<<"YES\n";
else
cout<<"NO\n";

}

return 0;
}


how you can say that if n is odd it will be palindrome.

You need to choose two indices and swap them.
So you can pick one of these indices to be (n+1)/2 th index(1 indexing) and other index which u want to swapâ€¦it doesnt matter if (n+1)/2 th index is 1 or 0 if n is odd.
So whichever index you want to change from 0 to 1 or 1 to 0, you can always swap it with the (n+1)/2 th index.