PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Jeevan Jyot Singh
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
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
YESwhen 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
YESif X=Y or X and Y are both even. Else, the answer isNO.
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;
}