Last Updated: 21 Nov, 2020
Add binary strings
Easy
Asked in companies
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
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.