Problem #67: Add Binary

Intuition & Strategy Breakdown

Traverse both binary strings from right to left with a carry variable. Compute bit sum and carry using sum % 2 and sum // 2, building the result string.

Python Solution

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        carry = 0
        i, j = len(a) - 1, len(b) - 1

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

Java Solution

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry != 0) {
            if (i >= 0) {
                carry += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                carry += b.charAt(j--) - '0';
            }
            res.append(carry % 2);
            carry /= 2;
        }
        return res.reverse().toString();
    }
}