Add Binary: Right-to-Left Addition with Carry

Add Binary is LeetCode 67. You are given two binary strings a and b, and you need to return their sum as a binary string.

Example: a = "11", b = "1" returns "100". Another: a = "1010", b = "1011" returns "10101".

This is the same column addition you learned in elementary school, but in base 2 instead of base 10. The carry can only ever be 0 or 1, and each column sums to at most 3 (1 + 1 + 1 carry).

The approach

You cannot convert the strings to integers and add them. Binary strings in this problem can be up to 10,000 characters long, which overflows any fixed-width integer type. You need to do the addition digit by digit.

The key insight: addition works right to left. Start two pointers at the end of each string and walk them backward. At each position, add the two digits plus any carry from the previous column. The current digit of the result is total % 2, and the carry for the next column is total // 2.

Here is the process:

1. Place pointer i at the last index of a and pointer j at the last index of b
2. Initialize carry = 0
3. While either pointer is valid or carry is nonzero, compute the column sum
4. Append each result digit to a list
5. After the loop, reverse the list and join it into a string

Because you build the result from the least significant bit to the most significant bit, you need to reverse it at the end. Alternatively, you can prepend to a string, but appending and reversing is more efficient.

Visual walkthrough

Here is the addition of a = "11" and b = "1", which should produce "100". Watch how the carry propagates through each column and extends the result by one digit at the end.

Each step follows the same logic: grab the current digit from each string (or 0 if that string is exhausted), add them with the carry, write total % 2, and update the carry to total // 2. The loop body never changes.

The solution

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

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

    return ''.join(reversed(result))

The loop condition while i >= 0 or j >= 0 or carry is critical. The or carry clause handles the case where both strings are exhausted but a carry of 1 still needs to be written. Without it, adding "11" and "1" would produce "00" instead of "100".

Inside the loop, each pointer is checked independently. If i is still valid, you add a[i] to the total and decrement i. Same for j. This naturally handles strings of different lengths without any special branching.

The result is built in reverse order (least significant bit first), so a final reversed() call puts the digits in the correct order.

Complexity analysis

Time: O(max(m, n)) where m and n are the lengths of strings a and b. You visit each character in both strings exactly once. The final carry step adds at most one more iteration.

Space: O(max(m, n)) for the result list. The output has at most max(m, n) + 1 characters (the +1 accounts for a potential final carry digit).

Edge cases

• Different lengths. a = "1", b = "1010". The shorter string runs out first. You treat its missing positions as 0, so the remaining digits of the longer string are added with just the carry.
• Both are "0". a = "0", b = "0" returns "0". The sum is 0 with no carry, producing a single "0".
• Carry extends the result. a = "11", b = "1" returns "100". Both strings are exhausted after two columns, but the leftover carry of 1 produces an extra leading digit. The or carry in the loop condition handles this.
• Single digit each. a = "1", b = "1" returns "10". The simplest case that produces a carry. a = "0", b = "1" returns "1". No carry needed.

The building blocks

This problem is built from two core building blocks:

Right-to-left digit addition. Walk two sequences from their ends toward their beginnings, processing one position at a time. When one sequence is shorter, treat its missing positions as 0. This pattern appears in any problem that involves arithmetic on numbers represented as strings or arrays, including Add Two Numbers (linked lists), Plus One, and Multiply Strings.

Carry propagation. At each position, compute a total and split it into a result digit (total % base) and a carry (total // base). The carry feeds into the next column. After all positions are processed, flush any remaining carry. This logic is identical in base 2, base 10, or any other base.

These two building blocks combine to handle the entire problem. The pointer logic handles traversal. The carry arithmetic handles the math. Each one is simple in isolation, and together they cover every case.

From understanding to recall

You can probably read through this solution and understand every line. That is the easy part. The hard part is reproducing it from scratch under time pressure without looking at any reference.

The right-to-left pointer setup, the or carry loop condition, the % 2 and // 2 arithmetic, the reverse at the end. Each of these is a small detail, but forgetting any one of them produces a wrong answer. The only way to make this automatic is repetition: type the solution from memory, verify it, and do it again after a few days.

Related posts

• Add Two Numbers - The same carry-based digit addition, but on linked lists instead of strings. If you can solve Add Binary, you already understand the core of Add Two Numbers.
• Plus One - A simpler version of digit-by-digit arithmetic on an array, where you only add 1 instead of a second number. The carry propagation logic is identical.