# XORPAL - Editorial

Setter: Jeevan Jyot Singh
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan

Simple

XOR operation

# PROBLEM:

A (1-indexed) binary string S of length N is called an xor palindrome if the value of S_i β S_{(N+1-i)} is same for all 1 \leq i \leq N.

You are given a binary string S of length N. Determine if it is possible to rearrange it to form an xor palindrome or not.

# QUICK EXPLANATION:

• For a string of odd length, the answer is YES.
• For a string of even length, the answer is YES when the count of 0 is equal to the count of 1 or the counts of 0 and 1 are even.

# EXPLANATION:

Observation

We can rearrange the string in any way. This means that the answer depends on the count of 0 and the count of 1 in the given string.

String is of odd length
Observation

The string would have a middle character at position i = (\frac{N}{2} +1). For this i, the value (N+1-i) = i. This means that irrespective of the value of S_i, S_i = S_{(N+1-i)} and S_i β S_{(N+1-i)} = 0.

If S_i β S_{(N+1-i)} = 0 for one value of i, we have to arrange the string such that S_i β S_{(N+1-i)} = 0 for all other i as well. Thus, we need to make S_i = S_{(N+1-i)} for all 1 \leq i \leq N.

Let X and Y denote the counts of 0 and 1 in the original string respectively. Since the length of the string (N) is odd, and X+Y=N, one number amongst X and Y is odd and the other is even.

In this case, we can always find an arrangement leading to an xor palindrome. How?

Suppose X is odd. We place all X zeros together. Now, since Y is even, \frac{Y}{2} is an integer. We can place \frac{Y}{2} ones at the beginning of the string and the remaining \frac{Y}{2} ones at the end of the string. This way, S_i β S_{(N+1-i)} = 0 for all 1 \leq i \leq N.

The case when X is even and Y is odd would be symmetric to the one explained above.

String is of even length

Let X and Y denote the counts of 0 and 1 in the original string respectively. Since the length of the string (N) is even, and X+Y=N, we have two cases:

• X and Y are both even: We can place all the zeros and ones such that S_i = S_{(N+1-i)}. This would make S_i β S_{(N+1-i)} same (0) for all 1 \leq i \leq N and give us an xor palindrome.
• X and Y are both odd: The value S_i β S_{(N+1-i)} can either be 0 or 1.
Suppose we want to make S_i β S_{(N+1-i)} = 0 for all 1 \leq i \leq N. This means that S_i = S_{(N+1-i)}. But since the number of zeros and ones is odd, this would not be possible.
If we want to make S_i β S_{(N+1-i)} = 1 for all 1 \leq i \leq N, we have to ensure S_i \neq S_{(N+1-i)}. This is possible only if for every 0, we have a 1 and vice versa. In other words, this is possible only when X=Y.
Conclusion

Let X and Y denote the counts of 0 and 1 in the original string respectively.

• If the string is of odd length, the answer is YES.
• If the string is of even length, we check the values X and Y. The answer is YES if X=Y or X and Y are both even. Else, the answer is NO.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

void solve()
{
int n; cin >> n;
string s; cin >> s;
array<int, 2> cnt{};
for(char c: s)
cnt[c - '0']++;
if(n % 2 == 1)
cout << "YES\n";
else if((cnt[0] % 2 == 0 and cnt[1] % 2 == 0) or cnt[0] == cnt[1])
cout << "YES\n";
else
cout << "NO\n";
}

int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
solve();
}
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;
while(t--) {
int n; cin >> n;
string s; cin >> s;
int cnt[2] = {0, 0};
for(int i = 0; i < n; i++) cnt[s[i] - '0']++;
cout << ((n&1) || cnt[0] == cnt[1] || (cnt[0]&1) + (cnt[1]&1) == 0?"YeS":"NO") << "\n";
}
return 0;
}

Editorialist's Solution
#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;

int oneCnt = 0;
int zeroCnt = 0;
for(int i = 0; i<n; i++){
if(s[i]=='0') zeroCnt++;
else oneCnt++;
}

if(n%2 || oneCnt%2==0 || oneCnt==zeroCnt){
cout<<"YES";
}
else{
cout<<"NO";
}

cout<<endl;
}
return 0;
}


when I solved this program in c language with same logic ,I got tle error.how can I resolve this?

Yo, whatβs this?

char s[n], i;

i is a Variable of type char. It should have been int, right?

yes.thank you. Itβs working now.

2 Likes