Add Binary

The carry is the whole algorithm; alignment and output order are the rest.

The contract and the shortest useful answer

You receive two binary strings, a and b, and must return their sum as another binary string. The inputs contain only '0' and '1', have lengths from 1 to 10^4, and have no leading zeroes except for the string "0".

The direct Add Binary solution is ordinary column addition:

1. Start at the rightmost bit of both strings.
2. Read a missing bit as 0 when one string is shorter.
3. Add the two bits and the incoming carry.
4. Emit total % 2 as the current result bit.
5. Propagate total // 2 as the carry for the next column to the left.
6. Continue while either string still has bits or a carry remains.
7. Reverse the collected bits.

In compact form:

carry = 0

while a or b or carry:
    total = bit_a + bit_b + carry
    emit total % 2
    carry = total // 2

reverse the emitted bits

This is a state-tracking problem. The strings provide the current input bits; the only evolving summary you need is carry.

Recognize manual addition in string form

A binary string is already aligned for column arithmetic: its rightmost character is its least-significant bit.

Consider:

  11
+ 01
----
 100

The rightmost column is 1 + 1 = 2, so we write 0 and carry 1. The next column is 1 + 0 + 1 = 2, so we write another 0 and carry 1 again. That final carry becomes the leading 1.

The order matters. A column cannot be finalized until the column to its right has passed its carry to it. That makes right-to-left scanning the natural dependency order.

A left-to-right scan is awkward because a carry discovered later could force you to revise output you already produced. You can make that approach work with extra bookkeeping, but it fights the representation instead of using it.

The important recognition cue is:

Each position depends on its two current digits plus a small amount of state from the position immediately to the right.

That state is the carry.

This is closely related to adding digits in the linked-list version of the problem. The reusable idea is the same, but the representation changes the mechanics. Here, the digits are accessed through string indices rather than linked-list nodes.

Python can also convert binary strings with int(a, 2), add the resulting integers, and convert back with bin. That is a valid language shortcut for this particular runtime, but it hides the mechanism the problem is testing. For an interview, explicit carry simulation gives you a solution you can explain, debug, and adapt.

Turn each column into explicit state

There are four obligations to make visible:

• i points to the current bit in a.
• j points to the current bit in b.
• carry moves information from the processed column to the next column.
• result stores the output bits discovered so far.

Initialize:

i = len(a) - 1
j = len(b) - 1
carry = 0
result = []

When an index is negative, that string has no bit left at the current position. Treating the missing bit as zero avoids padding either input:

bit_a = int(a[i]) if i >= 0 else 0
bit_b = int(b[j]) if j >= 0 else 0

Then one column follows the exact arithmetic:

total = bit_a + bit_b + carry
output_bit = total % 2
carry = total // 2

Why do these two operations work?

Binary division by 2 gives:

total = 2 * carry + output_bit

The remainder, total % 2, is the bit that belongs in the current position. The quotient, total // 2, is what must move into the next position.

The loop condition must include the carry:

i >= 0 or j >= 0 or carry

If both inputs are exhausted but carry is still 1, there is one final result column to emit. Omitting that condition drops the leading bit in cases such as "11" + "1".

Because we scan from right to left, we discover the answer backward. Appending each bit to a list is simple and cheap; reverse the list once at the end.

State the invariant and prove the transition

An invariant is a condition that remains true after every loop iteration. It turns the implementation from a plausible sequence of statements into something you can check.

After each iteration, result contains the correct bits for all processed low-order columns, stored in reverse order, and carry is exactly the value that must enter the next unprocessed column to the left.

Each part maps to a variable:

• The processed columns are represented by the portions of a and b to the right of i and j.
• result stores their answer bits.
• carry stores the interaction between those processed columns and the next column.

Initialization

Before the first iteration:

• No columns have been processed.
• result is empty.
• carry is 0.

So the invariant holds: the processed answer is empty, and nothing needs to enter the first column.

Maintenance

For the current column, calculate:

total = bit_a + bit_b + carry

The binary division identity is:

total = (total // 2) * 2 + (total % 2)

Therefore:

• total % 2 is the correct bit for the current column.
• total // 2 is exactly the carry into the next column.

Appending the remainder preserves the correct processed bits. Updating carry preserves the information needed by the next iteration. Moving both indices left advances to the next column.

Termination

The loop ends only when:

i < 0
j < 0
carry == 0

At that point, both input strings have been fully consumed, and no unresolved carry remains. Every column has been resolved. The bits in result are correct but reversed because they were discovered from least significant to most significant, so reversing them produces the required binary string.

The invariant is also a debugging tool. If a result is wrong, ask:

1. Did I read the correct current bits?
2. Did I emit the remainder before replacing the carry?
3. Did I move both indices?
4. Did I keep processing while a carry remained?
5. Did I reverse exactly once?

Dry-run the carry propagation

Take:

a = "1010"
b = "1011"

The scan starts at the right edge.

Column from right	Bit from a	Bit from b	Incoming carry	Total	Emitted bit	Next carry
1	0	1	0	1	1	0
2	1	1	0	2	0	1
3	0	0	1	1	1	0
4	1	1	0	2	0	1
5	0	0	1	1	1	0

The emitted bits, in discovery order, are:

1, 0, 1, 0, 1

They are backward. Reverse them:

10101

So:

1010 + 1011 = 10101

Now check the unequal-length boundary:

  11
+  1
----
 100

The first column reads 1 and 1, producing output 0 and carry 1. On the next iteration, b has no bit left, so its current value is treated as 0:

1 + 0 + 1 = 2

That emits another 0 and keeps the carry at 1. Both strings are then exhausted, but the loop runs once more because of the carry:

0 + 0 + 1 = 1

The output bits discovered are 0, 0, 1, which reverse to "100".

Three bugs appear often here:

• Stopping when both indices are exhausted: this drops a final carry.
• Reversing during every iteration: this creates unnecessary work and makes ordering harder to reason about.
• Updating carry before recording the current remainder: this mixes the current column with the next one.

Read the error. Trace the state. Fix the assumption.

Implement the Add Binary solution in Python

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

        while i >= 0 or j >= 0 or carry:
            bit_a = int(a[i]) if i >= 0 else 0
            bit_b = int(b[j]) if j >= 0 else 0

            total = bit_a + bit_b + carry
            carry, output_bit = divmod(total, 2)

            result.append(str(output_bit))

            i -= 1
            j -= 1

        return "".join(reversed(result))

divmod(total, 2) expresses the transition directly:

carry, output_bit = divmod(total, 2)

The quotient is the next carry, and the remainder is the current binary digit. The variable order mirrors the arithmetic identity, so there is less room to accidentally swap the two values.

The conditional reads make unequal lengths an ordinary case. No input padding is required, and the original strings remain unchanged.

The two lines worth checking first during debugging are:

while i >= 0 or j >= 0 or carry:

and:

carry, output_bit = divmod(total, 2)

The first controls termination. The second controls the state transition. If either is wrong, the whole result is wrong.

A shorter Python implementation could use int(a, 2) and bin, but I would keep the explicit version in an interview. It demonstrates the carry simulation, handles the representation directly, and transfers cleanly to languages or settings where integer conversion is not the intended path.

Complexity, edge cases, and the interview check

Let:

• m = len(a)
• n = len(b)

The loop processes at most max(m, n) + 1 columns. The extra column is possible when a final carry extends the result.

Time complexity

The algorithm performs constant work per processed column:

O(max(m, n))

Reversing and joining the output also take linear time, so the total remains O(max(m, n)).

Space complexity

The scalar state—indices, carry, and the current totals—uses:

O(1)

The output list and returned string require:

O(max(m, n))

That output-sized storage should be reported separately from the constant-sized working state. Calling the entire implementation O(1) space would ignore the result it must construct.

Edge cases to check

Case	What it verifies
"0" + "0"	The zero result is preserved
Equal-length strings	Both indices move together normally
Unequal lengths	Exhausted inputs are treated as zero
No carry	Each output bit is simply the current sum modulo two
Carry through several positions	The carry remains part of every next-column total
Final carry	The loop emits a new leading "1"

The input contract already guarantees valid binary characters and the allowed leading-zero behavior. Do not add character validation or arbitrary normalization unless the problem asks for it. Extra code creates extra branches without solving an obligation in this contract.

The interview checklist is short:

• Align the inputs from the right.
• Start carry at zero.
• Treat missing bits as zero.
• Emit total % 2.
• Propagate total // 2.
• Continue while a carry remains.
• Reverse the collected bits once.
• State O(max(m, n)) time and output-sized space.

The transferable rule is broader than binary addition:

When each position depends on the current values plus a bounded summary from the previous position, process positions in dependency order and name the invariant before coding.

Here, the summary is carry. The rest is disciplined bookkeeping: alignment, transition, termination, and reversal. Find that small piece of state, and a string that first looks like a formatting problem becomes ordinary arithmetic you can trace and prove.