67. Add Binary

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

The input strings are both non-empty and contains only characters 1or 0.

Example 1:

Input: a = "11", b = "1"

Output: "100"

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

Thoughts: Carry ripple adder

class Solution {

    // carry ripple adder
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while(i >= 0 || j >= 0){
            int sum = carry;
            if(i>=0) sum += a.charAt(i--) - '0';
            if(j>=0) sum += b.charAt(j--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if(carry > 0 ) sb.append(carry);
        return sb.reverse().toString();
    }
}

Python:

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        res = []

        i, j = len(a) - 1, len(b) - 1;
        carry = 0

        while i >= 0 or j >= 0:
            total = carry
            if i >= 0: 
                total += int(a[i])
                i -= 1
            if j >= 0:
                total += int(b[j])
                j -= 1
            res.append(`total % 2`)
            carry = total / 2

        if carry:
            res.append(`carry`)

        return "".join(res)[::-1]