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.