### PROBLEM LINK:

**Author:** Dymtro Berezein

**Testers:** Istvan Nagy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Easy

### PREREQUISITES:

binary operations

### PROBLEM:

Chef has a string A. He wants the string to convert into string B by applying the following operations as many times as needed. In each operation, we choose two indices i, j, i \neq j.

result = A_i \, op \, A_j

A_i = result \, op \, A_i

A_j = result \, op \, A_j

op operation could be bitwise AND, XOR or OR operation.

Find out minimum number of operations required or state if it is impossible.

### QUICK EXPLANATION:

If A = B, then no operation is required. In fact, problem guarantees that A \neq B.

If A consists of all 1’s or all 0’s, then you can’t convert it to B, as A won’t change with the operations.

Let cnt_0 denote the number of indices where A_i and B_i differ and A_i = 0.

Let cnt_1 denote the number of indices where A_i and B_i differ and A_i = 1.

Then, answer will be max(cnt_0, cnt_1).

### EXPLANATION:

If A = B, then no operation is required. In fact, problem guarantees that A \neq B.

If A consists of all 1’s or all 0’s, then you can’t convert it to B, as A won’t change with the operations.

**Understanding of operations**

Let us try to understand what these operations do?

**OR operation:**

result = A_i \, OR \, A_j

A_i = result \, OR \, A_i

A_j = result \, OR \, A_j

Which is equivalent to

result = A_i \, OR \, A_j

A_i = result

A_j = result

i.e. either A_i or A_j is 1, you can make both of them equal to 1.

**AND operation:**

result = A_i \, AND \, A_j

A_i = result \, AND \, A_i

A_j = result \, AND \, A_j

Which is equivalent to

result = A_i \, AND \, A_j

A_i = result

A_j = result

i.e. either A_i or A_j is 0, you can make both of them equal to 0.

**XOR operation**

result = A_i \, XOR \, A_j

A_i = result \, XOR \, A_i

A_j = result \, XOR \, A_j

Which is equivalent to

result = A_i \, XOR \, A_j

A_i = result \, XOR \, A_i = A_j

A_j = result \, XOR \, A_j = A_i

i.e., you can swap any two elements A_i, A_j, note that this operation will be useful if one of them is 0 and other 1.

**Take some example**

Let us take some example.

```
0 0 0 1 1
1 1 1 0 0
```

Note that you can not make any operation only among first three zeros to make all of these ones. You can swap first 0 and fourth 1, using XOR operation. After that swap second 0 and fifth 1. Now you will end up with

```
1 1 0 0 0
1 1 1 0 0
```

Now, you can take first one and third zero, and replace third number by 1, by using OR operation. You will end up with

```
1 1 1 0 0
1 1 1 0 0
```

So, in total we required three operations.

**Final solution**

Let cnt_0 be number of indices i, where A_i = 0 and B_i = 1.

Let cnt_1 be number of indices i, where A_i = 1 and B_i = 1.

Let us think about the cnt_0 elements, where A_i = 0 and B_i = 1. We have to change all of these zeros into ones. Note that this will require at least cnt_0 operations.

Let us think about the cnt_1 elements, where A_i = 1 and B_i = 0. We have to change all of these ones into zeros. Note that this will require at least cnt_1 operations.

Let op = max(cnt_0, cnt_1). We can make the A an B equal in op operations as follows.

- Let cnt_0 \geq cnt_1. Take cnt_1 0’s and cnt_1 1’s in A and apply the XOR operation to swap 0’s with 1’s. After that you will be left with total cnt_0 - cnt_1 zeros elements to change to one. That you can do by taking each of these zeros with some single one and applying the OR operation.
- Other case can be handled respectively.

### Time Complexity:

\mathcal{O}(n) for iterating over both the strings, where n is size of strings A or B.