Header Ads Widget

Maximise XOR | codechef solution

 

Problem

Chef has two binary strings  and , each of length .

Chef can rearrange both the strings in any way. Find the maximum bitwise XOR he can achieve if he rearranges the strings optimally.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of two lines:
    • The first line of each test case contains binary string .
    • The second line of each test case contains binary string .

Output Format

For each test case, output the maximum bitwise XOR of the strings in binary representation.

Constraints

  • 11000
  • 15105
  • Strings  and  consist only of 0 and 1.
  • The sum of  over all test cases do not exceed 5105.

Sample 1:

Input
Output
4
0011
1011
100
100
11111
11101
1
0
1110
110
10000
1

Explanation:

Test case 1: Rearranging string  as 0011 and string  as 1101, the XOR of the strings is 00111101=1110. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case 2: Rearranging string  as 010 and string  as 100, the XOR of the strings is 010100=110. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case 3: Rearranging string  as 11111 and string  as 01111, the XOR of the strings is 1111101111=10000. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case 4: Rearranging string  as 1 and string  as 0, the XOR of the strings is 10=1. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Code(C++):-

#include <iostream>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
     string a,b;
     cin>>a>>b;
     int zeros=0,ones=0;
     for(int i=0;a[i];i++)
     {
     if(a[i]=='0') zeros++;
     else if(a[i]=='1') ones++;
     if (b[i]=='0') zeros++;
     else ones++;
     }
     string ans="";

     int mn=min(zeros,ones);
     for(int i=0;i<mn;i++)
     ans+='1';
     for(int i=mn;i<a.length();i++)
     ans+='0';
     cout<<ans<<endl;
    
    }
    return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-