64. Add Binary

Add the two binary numbers exactly like grade-school addition, from the least significant bit to the most: sum the two bits plus any carry, write down sum mod 2, and carry sum divided by 2.

Idea

Binary addition is ordinary column addition in base 2. Walk both strings from the right, adding the current bits and the incoming carry. Each column produces a result bit (total % 2) and a new carry (total // 2). Continue until both strings are exhausted and there's no carry left.

Algorithm

1. i = len(a)-1, j = len(b)-1, carry = 0, result = [].
2. While i >= 0 or j >= 0 or carry:
   • total = carry (+ a[i] if in range, + b[j] if in range).
   • Append str(total % 2); set carry = total // 2; decrement i, j.
3. Reverse result and join.

Worked example: a = "1010", b = "1011"

Reading the bits bottom-to-top: "10101" (10 + 11 = 21).

Complexity

• Time: O(max(|a|, |b|)).
• Space: O(max(|a|, |b|)) for the result.

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