Add Binary — Solution

Problem

Given two non-empty binary strings, return their sum as a binary string. The strings contain only '0' and '1' characters and have no leading zeros (except for the string "0" itself).

• Input: a = "11", b = "1"
• Output: "100"
• Explanation: 3 + 1 = 4, which is 100 in binary.

Another example:

• Input: a = "1010", b = "1011"
• Output: "10101"
• Explanation: 10 + 11 = 21, which is 10101 in binary.

Intuition

This is elementary school addition, but in base 2 instead of base 10. Start from the least significant (rightmost) bit, add the two digits plus any carry from the previous position, write down the result bit (total % 2), and pass the carry (total // 2) to the next position. The key insight: a carry can only be 0 or 1 in binary, so you never need more than one extra digit for the carry — just loop until both strings and any remaining carry are exhausted.

Solution — Bit-by-Bit Simulation

Walk both strings from right to left simultaneously, adding corresponding digits and a running carry. When one string runs out, treat missing digits as 0. Collect result bits in a list and reverse at the end.

1. Set pointer left to the last index of a, and right to the last index of b. Initialize carry = 0 and an empty result list.
2. Loop while either pointer is in-bounds or carry is non-zero.
3. Read digit_a from a[left] (or 0 if out-of-bounds) and digit_b from b[right] (or 0 if out-of-bounds). Decrement both pointers.
4. Compute total = digit_a + digit_b + carry. Append total % 2 to the result and set carry = total // 2.
5. After the loop, reverse the result list and join into a string.

1def addBinary(self, a: str, b: str) -> str:
2    left = len(a) - 1
3    right = len(b) - 1
4    carry = 0
5    result = []
6
7    while left >= 0 or right >= 0 or carry:
8        digit_a = int(a[left]) if left >= 0 else 0
9        digit_b = int(b[right]) if right >= 0 else 0
10        total = digit_a + digit_b + carry
11        result.append(str(total % 2))  # current bit
12        carry = total // 2             # pass overflow to next position
13        left -= 1
14        right -= 1
15
16    return ''.join(reversed(result))

Time: O(max(n, m)) — each character in both strings is visited exactly once.

Space: O(max(n, m)) — the result string holds at most max(n, m) + 1 characters.

Complexity Summary

Common Mistakes

• Forgetting to flush the carry after both strings are exhausted — "1" + "1" should give "10" but without the final carry loop iteration you'd get "0". The loop condition must check carry in addition to the two pointers.
• Using Python's int(a, 2) shortcut in Java or C++ — works fine in Python which has arbitrary-precision integers, but causes integer overflow in Java/C++ for binary strings longer than 63 bits.
• Prepending to a string inside the loop — result = bit + result looks clean but is O(n) per prepend, making the total O(n²). Append to a list (or StringBuilder in Java) and reverse once at the end instead.
• Decrementing only the longer string's pointer — when one string runs short, you must still decrement both pointers each iteration; the out-of-bounds check (if left >= 0) handles the missing digit, not pointer manipulation.
• Reading a[left] - '0' without the out-of-bounds guard — accessing a negative index in C++ is undefined behavior; in Python it wraps around silently. Always check left >= 0 before reading a[left].

Related Problems

• add-two-numbers — same carry-propagation pattern, but digits are stored in linked list nodes instead of string characters
• multiply-strings — extends positional digit arithmetic to multiplication; the same right-to-left indexing applies
• reverse-bits — direct bit manipulation on an integer's binary representation
• number-of-1-bits — counting set bits in a binary number, uses the same conceptual understanding of binary representation
• counting-bits — computing bit counts for a range of numbers, reinforces binary addition patterns