67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:

The idea is to add each digit and calculate the carry.

Notice that the digit is sum % base, new carry is sum / base.



Code:

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int len1 = a.length() - 1;
        int len2 = b.length() - 1;
        int carry = 0;
        while (carry == 1 || len1 >= 0 || len2 >= 0) {
            int v1 = len1 >= 0 ? a.charAt(len1--) - '0' : 0;
            int v2 = len2 >= 0 ? b.charAt(len2--) - '0' : 0;
            int sum = v1 + v2 + carry;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}