Add binary strings

Easy
0/40
Average time to solve is 15m
79 upvotes
Asked in companies
FacebookMicrosoftSamsung R&D Institute

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2
10 01
3 2
111 10
Sample Output 1:
11
1001
Explanation of sample input 1:
In the first test case, the first string is “10” which is 2 in the decimal format, and the second string is “01” which is 1 in the decimal format. So, 2 + 1 = 3, which is represented as “11” in binary form.

In the first test case, the first string is “111” which is 7 in the decimal format, and the second string is “10” which is 2 in the decimal format. So, 7 + 2 = 9, which is represented as “1001” in binary form.
Sample Input 2:
2
3 1
111 0
1 1
1 1
Sample Output 2:
111
10
Explanation for sample input 2:
In the first test case, the first string is “111” which is 7 in the decimal format, and the second string is “0” which is 0 in the decimal format. So, 7 + 0 = 0, which is represented as “111” in binary form.

In the first test case, the first string is “1” which is 1 in the decimal format and the second string is “1” which is 1 in the decimal format. So, 1 + 1 = 2, which is represented as “10” in binary form.
Hint

Can you think of using the standard algorithm for the addition?

Approaches (1)
Bit Addition

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”
00000
00110
01010
01101
10010
10101
11010
11111

 

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

 

Steps are as follows:

 

  1. 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.
  2. 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).
  3. If “CARRY” is 1, append ‘1’ at the end of the “SUM” string.
  4. Reverse the “SUM” string and return it.
Time Complexity

O(N + M), Where ‘N’ and ‘M’ are the lengths of binary strings ‘A’ and ‘B’ respectively.

 

Since we will be scanning through both the strings once, the overall time complexity will be O(N + M).

Space Complexity

O( max(N, M) ), Where ‘N’ and ‘M’ are the lengths of binary strings ‘A’ and ‘B’ respectively.

 

Since we will be storing the sum in a binary string, since, the length of that string can be max(N, M) + 1 in the worst case, and the overall space complexity will be O( max(N, M) ).

Code Solution
(100% EXP penalty)
Add binary strings
Full screen
Console