#
PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

**Author:** utkarsh_25dec

**Testers:** IceKnight1093, tejas10p

**Editorialist:** IceKnight1093

#
DIFFICULTY:

1229

#
PREREQUISITES:

None

#
PROBLEM:

Given two binary strings A and B, find the maximum possible value of A\oplus B if both strings can be rearranged as you wish.

#
EXPLANATION:

Since we’d like to maximize the xor, we’d like to have as many 1's as possible.

We can obtain a 1 by:

- Pairing a 0 in A with a 1 in B
- Pairing a 1 in A with a 0 in B

Now, let A_0 and A_1 be the count of 0's and 1's in A. Similarly define B_0 and B_1.

Notice that we can obtain at most \min(A_0, B_1) ones of the first type, and \min(A_1, B_0) ones of the second type.

Of course, it’s always possible to attain exactly these many ones since they’re independent.

So, our final string has \min(A_0, B_1) + \min(A_1, B_0) ones, and then every other character is 0.

To maximize the xor, place all the ones before the zeroes.

#
TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

#
CODE:

##
Code (Python)

```
for _ in range(int(input())):
a = input()
b = input()
n = len(a)
a0, a1 = a.count('0'), a.count('1')
b0, b1 = b.count('0'), b.count('1')
ones = min(a0, b1) + min(a1, b0)
print('1'*ones + '0'*(n - ones))
```

2 Likes

Why am I getting time limit exceeded?

```
#include <bits/stdc++.h>
using namespace std;
void solution()
{
string A, B, C = "";
cin >> A >> B;
int one = 0, zero = 0, length = A.length();
for(int i = 0; i < length; i++)
{
if(A[i] == '1')
{
one++;
}
else
{
zero++;
}
if(B[i] == '1')
{
one++;
}
else
{
zero++;
}
}
int X = min(one, zero);
for(int i = 0; i < X; i++)
{
C = C + '1';
}
for (int i = 0; i<length - X; i++)
{
C = C + '0';
}
cout << C<< endl;
}
int main() {
// your code goes here
int T;
cin >> T;
while(T--)
{
solution();
}
return 0;
}
```

Your code has complexity \mathcal{O}(N^2) because `C = C + '1';`

(and `C = C + '0';`

) take \mathcal{O}(N) time, not \mathcal{O}(1).

Instead use `C += '1'`

and `C += '0'`

4 Likes

Thanks for your answer, the problem is solved. However, I have looked through Google about this and most of the answers say that x +=1 and x= x+1 are same. Please explain the time complexity of these two in short.

`a += b`

and `a = a + b`

are actually slightly different things if you look at what the operators mean.

`a += b`

means "apply the `+=`

operator on `a`

and `b`

. For integers, this means adding `b`

to `a`

. For strings, this means appending `b`

to `a`

(notice that it modifies `a`

, but doesn’t need to touch the existing characters in `a`

).

`a = a + b`

means "create the value `a + b`

, then assign it to `a`

".

For integers, this isn’t a problem because creating the value `a + b`

is easy, but it’s a problem for strings, since you create an entirely new string each time you append something.

For example, say you append `c`

N times to an empty string `S`

one by one using `S = S + 'c'`

- In the first iteration, it
*creates* the string `c`

, then assigns it to `S`

- In the second iteration, it
*creates* the string `cc`

then assigns it to `S`

- In the third iteration, it
*creates* the string `ccc`

then assigns it to `S`

\vdots

It’s easy to see that the total length of strings you create is 1 + 2 + 3 + \ldots + N = N(N+1)/2

You can test this yourself easily, just try running the code

```
string s = "";
for (int i = 0; i < 1000000; ++i) s += '0';
```

then replace the statement with `s = s + '0'`

and see what happens.

5 Likes

Thanks for the explanation.

The s += ‘0’ code runs fast whereas s = s + ‘0’ takes a loooong time and throws SIGTSTP

What is wrong with this code ?

It has passed all test cases for Sample 1 , but overall Result is WA

```
#include <bits/stdc++.h>
using namespace std;
string max_xor(string s1,string s2){
int cnt_0=0,cnt_1=0;
int n=s1.size();
string s3="";
for(int i=0;i<n;i++){
if(s2[i]=='1')
cnt_1++;
else
cnt_0++;
}
for(int i=0;i<n;i++){
if(s1[i]=='1'){
if(cnt_0>0)
{
cnt_0--;
s3+='1';
}
else
s3+='0';
}
else
{
if(cnt_1>0)
{
cnt_1--;
s3+='1';
}
else
s3+='0';
}
}
return s3;
}
int main() {
int T;
cin>>T;
while(T--){
string A,B;
cin>>A>>B;
cout<<max_xor(A,B)<<endl;
}
return 0;
}
```

Consider

```
1
101
000
```

where your code prints `101`

but the answer is `110`

.

You’re correctly computing the number of ones in the answer, they just might not be in the right positions.

Thanks a lot, for solving my query and providing the test case.

So to get all 1 at correct place we can use sorting [ Using 2 pointers to avoid Runtime error] in the final string.

OR

what else can we do to make this code work ? , other than using the same solution as in editorial.