Author :- divyesh196
Tester :- divyesh196
Editorialist :- divyesh196
Difficulty :- Cakewalk
Prerequisites :- Counting Frequency in an array or Sorting
Problem :- CodeChef: Practical coding for everyone
Solution
As we can permute any substring any number of times in given string , so if number of 1’s and 0’s in both the sustring are equal then it is always possible that after a definited number of operations both string will becom equal. So, we can simply count the number of 1’s and 0’s in both string and check if they are equal then print “Happy New Year” with quotes otherwise “-1”. Time Complexity of this approach will take O(n).
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll i,j;
int main()
{
ll t; // No. of test cases
cin>>t;
while(t--)
{
ll n; // No. of characters in both string
cin>>n;
unordered_map<char,ll>mp; // Map to count freuency of 1's and 0's in
// both string s1 and s2
mp.clear();
string s1,s2;
cin>>s1>>s2;
for(i=0;i<s1.length();i++)
{
mp[s1[i]]++; // Count of characters in s1
}
for(j=0;j<s2.length();j++)
mp[s2[j]]--;
if(mp['1']!=0 || mp['0']!=0) // If number of characters are not equal
cout<<-1<<endl;
else // If equal
{
cout<<"\"";
cout<<"Happy New Year";
cout<<"\""<<endl;
}
}
}