Description

Given two binary strings a and b, return their sum as a binary string.

Example 1:

1Input: a = "11", b = "1"
2Output: "100"

Example 2:

1Input: a = "1010", b = "1011"
2Output: "10101"

Constraints:

  • 1 <= a.length, b.length <= 10^4
  • a and b consist only of ‘0’ or ‘1’ characters.
  • Each string does not contain leading zeros except for the zero itself.

Solution

This is not straight forward and requires complicated logic for binary addition. One simple solution would be use to Integer addition. We can use Integer class with radix=2 to add binary numbers.

 1class Solution {
 2    public String addBinary2(String a, String b) {
 3        if (a == null || b == null)
 4            return null;
 5        if (a.length() == 0)
 6            return b;
 7        if (b.length() == 0)
 8            return a;
 9        Integer aInt = Integer.parseInt(a, 2);
10        Integer bInt = Integer.parseInt(b, 2);
11        return Integer.toString(aInt + bInt, 2);
12    }
13}

However, this may overflow Integer maximum limits. So, we have to use BigInteger class to replace Integer as shown in below snippet.

1        BigInteger aInt = new BigInteger(a, 2);
2        BigInteger bInt = new BigInteger(b, 2);
3        return aInt.add(bInt).toString(2);

Another option is to use complicated arithmetic.

 1class Solution {
 2    public String addBinary(String a, String b) {
 3        StringBuilder sb = new StringBuilder();
 4        for (int i = a.length() - 1, j = b.length() - 1, carry = 0; i >= 0 || j >= 0 || carry > 0; i--, j--) {
 5            if (i >= 0)
 6                carry += a.charAt(i) - '0';
 7            else
 8                carry += 0;
 9            if (j >= 0)
10                carry += b.charAt(j) - '0';
11            else
12                carry += 0;
13            sb.append(carry % 2);
14            carry = carry / 2;
15        }
16        return sb.reverse().toString();
17    }
18}