Problem Statement
Given two binary strings, return their sum (also a binary string).
For example,a = "11", b = "1"
Return "100".
Solution Explanation
The question is very straightforward where you add two binary values in string form. Carry is the only thing we needed to handle here carefully.
For example,
B1 101
B2 11
Carry 11
-------
Sum 1000
The algorithmic solution should be basically retrieve the last char from both the strings, get the integer value, add it to the sum, check if there's a carry, append the rest of the value to resultant string.
Here's how the code in java looks like,
public class AddBinary {
public static void main(String[] args) {
String s1="101";
String s2="11";
System.out.println("Binary addition of s1 and s2 is "+addBinary(s1,s2));
}
public static String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0)
sum += b.charAt(j--) - '0';
if (i >= 0)
sum += a.charAt(i--) - '0';
result.append(sum % 2);
carry = sum / 2;
}
if (carry != 0)
result.append(carry);
return result.reverse().toString();
}
}
Time Complexity
The time complexity is O(m+n) where m is the length of the binary string a and n is the length of the binary string b.