Add Binary · DSA Prep

The insight that unlocks this problem is that binary addition is the column addition you already know, in base 2. Line the two strings up on their right edges and walk from the least significant bit. Every column is identical: take the incoming carry, add the two digit bits, and reduce. Because the universe only has 0 and 1, whenever that running total reaches 2 the column cannot hold it as a single digit — so it keeps total mod 2 as its bit and passes the extra 1 (that is total // 2) to the next column on the left. That single rule, a carry in + two digits → one output bit + a carry out, is the whole algorithm, and it is why the loop must also keep running after both strings run dry: a live carry still needs a column to spill into.

Brute Force: Convert to Integers

Time O(n)Space O(n)

Leverage the runtime’s arbitrary-precision integers: parse each binary string as an integer, add them, and format the result back to a binary string.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return format(int(a, 2) + int(b, 2), "b")

That is two lines and always returns the right answer, so why is it the wrong tool for an interview? The constraint planks the strings at 10^4 digits — far beyond what a native 64-bit integer holds. Python backs this with big integers, but most languages overflow immediately, so a portable solution cannot rely on the conversion. And on the algorithmic front it is cheating the problem: the entire exercise is the carry logic, which the library does for you. The raw-digit conversion itself is also not free — large base-2 conversions can cost more than a linear scan. Counting the two conversions plus the formatting round-trip gives O(n) time and O(n) space, but the point of the problem is to implement the addition by hand instead of outsourcing it.

Manual Carry Loop

OptimalTime O(max(m, n))Space O(max(m, n))

Walk both strings from their right ends with two pointers and a single carry state. At every column, fold the carry together with the current digit of each string (a missing digit counts as 0), then emit total % 2 as the output bit and keep total // 2 as the carry for the next column. The loop runs while digits remain or a carry is still pending — the final iteration exists solely to write that spilled carry as a brand-new leading 1. Because every column does a constant amount of work and no re-scans happen, this is O(max(m, n)) time.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        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
            res.append(str(total % 2))
            carry = total // 2
        return "".join(reversed(res))

Watch the carry chip land on a = "11" and b = "1": the first column overflows into a carry that ripples two more columns left and finally spawns the extra leading bit that turns "11" + "1" into a three-digit sum.

setup · align both strings on the LSB

MSB

··

1·

LSB

Result registers

···

carry travels right to left: the carry-out of one column arrives as the carry-in of the column to its left — that is why the carry chip births indigo and fades to slate after it has moved on

1 / 5

currentseencomparingresult

The core idea: binary column addition is exactly the addition you learned for decimals, with a base of 2 and no digit above 1. Start at the LSB (least significant bit, the right end) and walk left. A column adds its incoming carry plus one a digit plus one b digit. Whenever that total reaches 2 or more, the column keeps only total mod 2 and passes the extra 1 to the next column to the left. Here a = 11 and b = 1 line up on the right, leaving one final column (position 2) empty on the far left — that empty column exists in case the last columns produce a carry.

Watch the longer case a = "1010" and b = "1011": two carries ripple left across five columns, and the very last one grows a brand-new most significant column — the exact situation the or carry clause in the while condition exists to handle.

setup · align both strings on the LSB

MSB

··

LSB

Result registers

·····

carry travels right to left: the carry-out of one column arrives as the carry-in of the column to its left — that is why the carry chip births indigo and fades to slate after it has moved on

1 / 7

currentseencomparingresult

Second and longer trace: a = 1010 (decimal 10) and b = 1011 (decimal 11) should sum to binary 10101 (decimal 21). Five columns are reserved because a 4-bit plus a 4-bit pair can overflow by one column. Everything runs on the identical rule: add the incoming carry and the two digits, write total mod 2, pass total divided by 2 left.

Why it is the right cost: each position is visited exactly once and performs O(1) work (one add, one mod, one division), so the loop runs once per column and time is O(max(m, n)) — no conversion, no repeated re-scanning. Space is O(max(m, n)) only because the result itself can be one bit longer than the longer input; beyond that output the algorithm holds just two pointers and the carry, so auxiliary space stays O(1). It also works in any language, because it never depends on integer width. Correctness follows from the base-2 column rule: writing total mod 2 and carrying total // 2 exactly reproduces the decimal-style algorithm you learned, so the bits assemble in their true order once reversed.