Add Binary

Problem

You are given two non-negative integers written as binary strings a and b. Return their sum, also as a binary string. Neither input has leading zeros (except the string "0" itself), and your output should follow the same rule. The two strings may have different lengths.

Examples

• a = "11", b = "1" → "100" — 3 + 1 = 4, which is 100 in binary.
• a = "1010", b = "1011" → "10101" — 10 + 11 = 21.
• a = "0", b = "0" → "0" — nothing to carry.

Constraints

• 1 <= a.length, b.length <= 10^4
• Each string consists only of '0' and '1', with no leading zeros beyond a lone "0".

Lengths up to 10^4 mean the sum can be about 10^4 bits wide. Python’s arbitrary-precision integers handle that, but the interview point is to add correctly without relying on a fixed-width integer type that would overflow.

Think about it first

TL;DR

Add column by column from the right with a carry — O(n) time, O(n) space — or fold with XOR/AND carry propagation.

Approach 1 — Arithmetic (parse, add, format)

Binary strings are just numbers: parse both, add, and format the result back in base 2.

def addBinary(a: str, b: str) -> str:
    return bin(int(a, 2) + int(b, 2))[2:]

Complexity: O(n) in Python (big-int add), O(1) extra space.

Why the constraints matter: this relies entirely on arbitrary-precision integers. With 10^4-bit inputs, a fixed-width int/long (32 or 64 bits) in most languages overflows, which is why interviewers ask for the manual version below.

Approach 2 — Column addition with a carry

The insight: you never need the whole number at once. Walk both strings from the least-significant end, keep a running carry, and at each column compute total = carry + bit_a + bit_b. The output bit is total & 1 (is the sum odd?) and the carry into the next column is total >> 1 (was it 2 or 3?).

def addBinary(a: str, b: str) -> str:
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    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
        out.append(str(total & 1))   # sum bit for this column
        carry = total >> 1           # carry into the next column
    return "".join(reversed(out))

Walkthrough on a = "1010", b = "1011" (adding right to left):

Collected bits are 1,0,1,0,1; reversed → "10101" = 21.

Complexity: O(n) time where n = max(len(a), len(b)), O(n) space for the output.

Approach 3 — XOR/AND carry propagation

The insight: addition on bit-vectors splits cleanly into two halves. x ^ y produces the sum in every column ignoring carries; x & y marks columns where both bits are 1, i.e. where a carry is generated, and shifting that left by one (<< 1) drops each carry into the next column. Re-add those two results and repeat; the carry word shrinks toward zero, and when it hits 0 the XOR already holds the full sum.

def addBinary(a: str, b: str) -> str:
    x, y = int(a, 2), int(b, 2)
    while y:                       # y holds the pending carries
        answer = x ^ y             # add columns, ignore carry
        carry = (x & y) << 1       # carries, moved one column left
        x, y = answer, carry
    return bin(x)[2:]

Walkthrough on x = 10 (1010), y = 11 (1011):

• answer = 1010 ^ 1011 = 0001; carry = (1010 & 1011) << 1 = 1010 << 1 = 10100. Now x=00001, y=10100.
• answer = 00001 ^ 10100 = 10101; carry = (00001 & 10100) << 1 = 0. Now x=10101, y=0 → stop.
• Result bin(21)[2:] = "10101".

Complexity: O(n) per pass and O(n) passes in the worst case of a rippling carry, so O(n^2) bit operations here — its value is conceptual (it mirrors how a hardware adder works), not speed.

Common pitfalls

• Dropping the final carry: the loop must keep going while carry (or y) is nonzero, or "11" + "1" loses the leading 1 and returns "00".
• Reversing at the wrong time: you build the answer least-significant bit first, so reverse (or insert(0, ...)) before joining.
• Assuming equal lengths: guard each index independently (if i >= 0), since the strings can differ in length.
• [2:] slice: bin(4) is "0b100"; forgetting to strip the "0b" prefix returns a malformed answer.

Pattern takeaway

Any addition decomposes into “sum without carry” (XOR) plus “carries, shifted one place left” (AND then << 1). Whether you simulate columns with a carry variable or fold whole words with XOR/AND, the model is the same, and it is the bridge from arithmetic to pure bit manipulation.