New update is available. Click here to update.

Last Updated: 21 Nov, 2020

Easy

```
The first line contains a single integer βTβ representing the number of test cases.
The second line contains two space-separated integers βNβ and βMβ which are the length of strings βAβ and βBβ respectively.
The third line of each test case will contain two space-separated binary strings βAβ and βBβ as described above.
```

```
For each test case, print the sum of the given binary strings in a binary form.
Output for every test case will be printed in a separate line.
```

```
You donβt need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N, M <= 5000
βAβ and βBβ consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.
Time limit: 1 sec
```

Approaches

The basic idea of this approach is to start doing bit by bit addition while keeping track of the carry bit from the least significant bits, i.e. from the end of the strings. Let say βaβ is the current bit of βAβ and βbβ is the current bit of βBβ and βcβ is the carry bit. Now, we want to add those bits and get the resulting βsumβ and new βcarryβ bits. Consider the boolean table:

βaβ | βbβ | βcβ | βsumβ | βcarryβ |

0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 | 0 |

0 | 1 | 0 | 1 | 0 |

0 | 1 | 1 | 0 | 1 |

1 | 0 | 0 | 1 | 0 |

1 | 0 | 1 | 0 | 1 |

1 | 1 | 0 | 1 | 0 |

1 | 1 | 1 | 1 | 1 |

After observing closely, we can find the βSUMβ is (βaβ + βbβ + βcβ) % 2 and βCARRYβ is (βaβ + βbβ + βcβ) / 2.

Steps are as follows:

- Initialise a βCARRYβ variable with zero which will store the carry and create an empty string βSUMβ to store the sum of both binary strings.
- Start iterating from the end of the strings.
- Let say we are currently considering the ith element from the end.
- Initialise a βCUR_SUMβ variable with zero to store the current sum.
- If the ith element exists for the string βAβ i.e. βiβ <= βNβ
- Add the value of that element in βCUR_SUMβ i.e. βCUR_SUMβ = βCUR_SUMβ + A[N - i]

- If the ith element exists for the string βB,β i.e. βiβ <= βMβ
- Add the value of that element in βCUR_SUMβ i.e. βCUR_SUMβ = βCUR_SUMβ + B[M - i]

- Add the previous carry to βCUR_SUMβ.
- Append (βCUR_SUMβ % 2) at the end of the βSUMβ string. And assign (βCUR_SUMβ / 2) to βCARRYβ i.e. βCARRYβ = (βCUR_SUMβ / 2).

- If βCARRYβ is 1, append β1β at the end of the βSUMβ string.
- Reverse the βSUMβ string and return it.