# Add binary strings

Posted: 21 Nov, 2020

Difficulty: Easy

#### You have been given two binary strings ‘A’ and ‘B’. Your task is to find the sum of both strings in the form of a binary string.

#### Binary strings are the representation of integers in the binary form. For example, the binary strings of 9 and 16 are “1001” and “10000” respectively.

##### Input Format:

```
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.
```

##### Output Format:

```
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.
```

##### Note:

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

##### Constraints:

```
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
```

Approach 1

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.

SIMILAR PROBLEMS

# Palindromes And Indexes

Posted: 7 Jul, 2021

Difficulty: Moderate

# Ninja's Frustrating Homework

Posted: 8 Jul, 2021

Difficulty: Ninja

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Hotel Rooms

Posted: 29 Jul, 2021

Difficulty: Moderate

# Matching Prefix

Posted: 21 Aug, 2021

Difficulty: Moderate