Chef And New Year | CodeChef

editorial
,
1

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;
                  }
     }

}