Add Binary
Add Binary: given two binary strings a and b, return their sum as a binary string. The inputs can be far longer than any integer type can hold.
- 1 <= a.length, b.length <= 10⁴
- a and b consist only of '0' or '1' characters
- Each string does not contain leading zeros except for the zero itself
Intuition
Column addition is the same in base 2 as in base 10 — walk both strings from the right, add the two digits and the carry, write sum % 2, and carry sum // 2. The only base-2 specialisation is that a column can reach 3, so the carry is still at most 1. Converting to an integer first is tempting and wrong: the constraints allow 10⁴ digits, far beyond a 64-bit type.
Digit-by-digit simulation is the move whenever the inputs are given as strings or lists and are explicitly allowed to exceed integer range. The tell is a length constraint far past 19 digits. Add Two Numbers, Plus One, and Multiply Strings are the same column arithmetic.
Approach
Before reading on: work out the largest value a single column can produce, and convince yourself the carry never exceeds 1. Then check what your code returns for "1" + "1" — the case where the answer is longer than either input.
Why the strings cannot be converted to integers
The natural-looking int(a, 2) + int(b, 2) works in Python, whose integers are arbitrary precision, but it is not the intended solution and it fails outright in C++ and Java, where 10⁴ binary digits overflow every primitive type by a factor of about 10³⁰⁰⁰. Even in Python it hides the algorithm the question is asking for. Treating the strings as digit sequences keeps the method identical in all three languages and independent of the word size.
One loop over both strings, right to left
Index from the end with a single pointer i counting down, and read a[len(a)-1-i] when that index exists, otherwise 0. This lets one loop handle unequal lengths without padding the shorter string first. At each step compute total = digit_a + digit_b + carry; append total % 2 to the result and set carry = total // 2. Because each digit is 0 or 1, total ranges over 0..3, so the carry is always 0 or 1 — the same invariant that makes decimal column addition work.
The final carry and the reversal
After the loop, a carry may remain — adding 1 and 1 produces 10, which is one digit longer than either input. Appending that final carry is what most incorrect solutions forget, and it only shows up on inputs whose sum gains a digit. Because digits were appended least-significant-first, the accumulated list must be reversed before joining. Building a list and reversing once is O(n); repeatedly prepending to a string would copy the whole result each time and degrade to O(n²).
Solution & live demo
Common pitfalls
Converting to integers first
return bin(int(a, 2) + int(b, 2))[2:]
add the digits column by column
With up to 10⁴ binary digits the value exceeds every fixed-width integer type, so this cannot be translated to C++ or Java at all. It also sidesteps the algorithm the question exists to test.
Dropping the final carry
while i >= 0 or j >= 0:
...
return "".join(reversed(result))while i >= 0 or j >= 0 or carry:
...When the top column carries, the answer is one digit longer than both inputs. Without or carry in the condition, "1" + "1" returns "0" instead of "10".
Prepending to a string in the loop
result = str(total % 2) + result
result.append(str(total % 2)) # reverse once at the end
Strings are immutable, so each prepend copies the entire accumulated result, making the loop O(n²). Appending to a list and reversing once stays linear.
Edge cases
One column, no carry, and the result is "0" rather than an empty string.
The missing digits read as 0, so no padding step is needed.
The leftover carry is appended, giving "10".
Each column carries into the next, producing "10000".
Digit-wise addition is unaffected; an integer conversion would overflow in C++ and Java.