1.

Add two Binary Strings and return a Binary String as a result. The addition should be performed as per the rules of binary addition.

Answer»

So, the question is basically to add 2 binary numbers given in the form of strings. We should know the basic rules of binary addition:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 and Carry = 1

This shows that whenever the result exceeds 1, the answer of addition becomes 0 and carry becomes 1. So, using these rules, we will add 2 binary strings starting from their LSBs i.e. from the last index of each string moving towards the first index.

Java Code for Binary Addition of Strings

import java.util.*;
class Main {

public static String add(String a, String b) {
String ans = "";

if(a.equals("0") && b.equals("0")) return "0";

int i = a.length() -1;
int j = b.length() -1;

int ca = 0;

while(i >=0 || j>=0 || ca >0) {

int d1 = (i >= 0) ? (a.charAt(i) - '0') : 0;
int d2 = (j >= 0) ? (b.charAt(j) - '0') : 0;

int digit = 0;
if(d1 + d2 + ca >= 2) {
digit = (d1 + d2 + ca) % 2;
ca = (d1 + d2 + ca) / 2;
} else {
digit = d1 + d2 + ca;
ca = 0;
}

i--;
j--;
ans = digit + ans;
}

return ans;
}

public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
String a = scn.nextLine();
String b = scn.nextLine();

System.out.println("The sum is: " + add(a,b));
}
}

Sample Output

Input:
1
0111

Output: The sum is: 1000


  • Corner Cases, You Might Miss: It is very important to address that the numbers might not be of equal length. As in the example shown above, the first number is 1 and the second is 0111. So, the first number is smaller than the second number. The second number can also be smaller than the first number. Also, even if the numbers of equal lengths are passed, the result of addition can exceed one bit. As in the example shown above, the larger number was a 3-bit number 111 and the output is a 4-bit number 1000.


  • Time Complexity: O(N) where N is the length of the longer string among the 2 input binary strings.


  • Auxiliary Space: O(1) as we have not used any extra space to solve our problem.


Discussion

No Comment Found

Related InterviewSolutions