Header Ads Widget

Maximise XOR | codechef solution

Rajnish Tripathi 06:30

 

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

  • 1≤�≤1000
  • 1≤�≤5⋅105
  • Strings � and � consist only of 0 and 1.
  • The sum of � over all test cases do not exceed 5⋅105.

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 0011⊕1101=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 010⊕100=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 11111⊕01111=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 1⊕0=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:-




Tags:

Post a Comment

0 Comments