LeetCode 67 – Add Binary

Add Binary looks like string manipulation and is really about carries. The version most people write first converts to an integer, adds, and converts back — which is correct for the examples, fails the constraints, and is the exact thing the problem is designed to rule out.

The problem

Given two binary strings a and b, return their sum as a binary string.

"11"    + "1"     -> "100"
"1010"  + "1011"  -> "10101"
"0"     + "0"     -> "0"
"1"     + "111"   -> "1000"      the carry runs all the way out

The constraint that matters: the strings can be up to 10⁴ characters. That is a number with thousands of bits, so Integer.parseInt(a, 2) and even Long.parseLong overflow long before you get there. BigInteger would work and is a fine thing to mention, but reaching for it as the answer sidesteps everything being asked.

Add it the way you were taught

Column by column from the right, carrying. Binary makes the carry table trivially small:

sum = bitA + bitB + carry     ranges over 0..3

  0 -> write 0, carry 0
  1 -> write 1, carry 0
  2 -> write 0, carry 1
  3 -> write 1, carry 1

so:  digit = sum % 2      carry = sum / 2

Two things make this cleaner than it first looks. Handle the unequal lengths inside the loop rather than padding the shorter string first — a padded copy is an allocation you do not need, and "read a 0 when the index has run out" is one conditional. And keep looping while either index is alive or the carry is set, which folds the final "1" of "1" + "111" into the same loop instead of a special case afterwards.

Java

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder out = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;

        // "|| carry != 0" is what handles the final carry out, e.g. "1" + "111".
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';    // past the end reads as 0
            if (j >= 0) sum += b.charAt(j--) - '0';

            out.append((char) ('0' + sum % 2));
            carry = sum / 2;
        }

        return out.reverse().toString();
    }
}

Digits come out least-significant first, so the result is reversed once at the end. StringBuilder.reverse() is O(n) and happens once; inserting at index 0 on every iteration would be O(n²), because each insert shifts everything already written. That is the performance difference worth naming out loud, and it is the same reason string concatenation in a loop is a trap in Java.

c - '0' converts a digit character to its value by ASCII arithmetic. Use it rather than Character.getNumericValue: it is what every reviewer expects to see, and it makes the "read past the end as 0" symmetry obvious.

Python

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        out = []
        i, j, carry = len(a) - 1, len(b) - 1, 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

            out.append(str(total % 2))
            carry = total // 2

        return "".join(reversed(out))

Build a list and "".join it. Python strings are immutable, so out += digit in a loop allocates a new string every iteration — the same O(n²) trap as Java's concatenation, wearing friendlier syntax.

Python can do bin(int(a, 2) + int(b, 2))[2:] and it is genuinely correct at any length, because Python integers are unbounded. Say it, and then say why it is not the answer: the interviewer wants the carry loop, and in most other languages the one-liner is simply wrong.

Doing it with bit operations

The carry loop generalises to a well-known trick for adding two integers with no + at all, which is the follow-up this problem sets up (LeetCode 371, Sum of Two Integers):

    int add(int x, int y) {
        while (y != 0) {
            int carry = (x & y) << 1;   // 1s where BOTH have a bit: those carry left
            x = x ^ y;                    // XOR is addition without the carry
            y = carry;                    // ...now add the carry in, and repeat
        }
        return x;
    }

Two ideas, both worth being able to state: XOR is addition per bit ignoring carries, and AND finds exactly the positions that generate a carry, which then shifts one place left. Loop until nothing carries. It terminates because each round pushes carries strictly leftwards.

It does not solve this problem — 10⁴ bits do not fit in an int — but it is the same insight at machine width, and volunteering the connection is exactly the kind of thing that turns an Easy into a good conversation.

Complexity

The output is one character longer than the longer input at most, since adding two n-bit numbers produces at most n + 1 bits. Ignoring the output the loop is O(1) in space.

What the interviewer is checking

• That you notice the length constraint rules out integer parsing.
• The carry loop, with sum % 2 and sum / 2.
• || carry != 0 in the loop condition, rather than a trailing special case.
• Unequal lengths handled by reading past the end as 0, with no padding allocation.
• That you build and reverse instead of prepending — the O(n²) trap.
• "0" + "0", and a carry that propagates the whole way.
• Bonus: XOR and AND as sum-without-carry and carry.