#67 Add Binary

frequently reported atGoogle Amazon Meta Microsoft

the problem

In plain words

a and b are non-negative numbers written in binary, as strings of '0' and '1'. Return their sum, also as a binary string.

in a = "11", b = "1"

out "100"

3 + 1 = 4.

in a = "1010", b = "1011"

out "10101"

10 + 11 = 21.

1 ≤ a.length, b.length ≤ 10⁴
Only the characters '0' and '1'
No leading zeros, except the number "0" itself

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSimulation Bit tricks (shift, mask, lowest set bit)

It's school addition in base 2. Start from the right end of both strings; each column adds two digits and the carry. The digit is sum % 2, the new carry is sum / 2. The strings can be 10,000 digits long, so never turn them into an int or long.

solutions

From brute force to optimal

Let BigInteger parse both strings in base 2, add, and print in base 2. Correct — but interviewers usually want you to do the adding.

new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2).

timeO(m + n)

Parsing, adding and printing are each linear for numbers of this size.

spaceO(m + n)

Two big numbers and the result.

javajava.math.BigInteger · java.util.*

1class Solution {2    public String addBinary(String a, String b) {3        // Correct for any length — but interviewers usually ask you not to use it.4        return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);5    }6}

Two pointers from the right, a carry, and a StringBuilder. Reverse once at the end.

i, j at the last digits; carry = 0.
While i ≥ 0 or j ≥ 0 or carry > 0: sum = carry + the digits under i and j (if any).
Append sum % 2; carry = sum / 2; move i and j left.
Reverse the builder.

timeO(max(m, n))

One O(1) step per column, plus one reverse at the end.

spaceO(max(m, n))

The answer itself: at most max(m, n) + 1 digits.

javajava.math.BigInteger · java.util.*

1class Solution {2    public String addBinary(String a, String b) {3        StringBuilder sb = new StringBuilder();4        int i = a.length() - 1, j = b.length() - 1, carry = 0;5        while (i >= 0 || j >= 0 || carry > 0) { // a digit left, or a carry to place6            int sum = carry;7            if (i >= 0) sum += a.charAt(i--) - '0';8            if (j >= 0) sum += b.charAt(j--) - '0';9            sb.append(sum % 2); // this column's digit: 0 or 110            carry = sum / 2; // sum 2 or 3 → carry 111        }12        return sb.reverse().toString(); // we wrote the digits right to left13    }14}

sim

Dry run

loading simulation…

javajava.math.BigInteger · java.util.*

1class Solution {2    public String addBinary(String a, String b) {3        StringBuilder sb = new StringBuilder();4        int i = a.length() - 1, j = b.length() - 1, carry = 0;5        while (i >= 0 || j >= 0 || carry > 0) { // a digit left, or a carry to place6            int sum = carry;7            if (i >= 0) sum += a.charAt(i--) - '0';8            if (j >= 0) sum += b.charAt(j--) - '0';9            sb.append(sum % 2); // this column's digit: 0 or 110            carry = sum / 2; // sum 2 or 3 → carry 111        }12        return sb.reverse().toString(); // we wrote the digits right to left13    }14}

The Sum of Two Integers loop on big numbers: x ^ y adds without carrying, (x & y) << 1 is the carry. Repeat until the carry is 0.

x, y = the two numbers.
While y ≠ 0: carry = (x & y) << 1; x = x ^ y; y = carry.
Print x in base 2.

timeO((m + n)²) worst case

Each round is O(m + n); the number of rounds is the longest carry chain + 1, which can be about n ("1111…1" + "1").

spaceO(m + n)

A few big numbers.

javajava.math.BigInteger · java.util.*

1class Solution {2    public String addBinary(String a, String b) {3        BigInteger x = new BigInteger(a, 2), y = new BigInteger(b, 2);4        while (y.signum() != 0) {                    // same loop as Sum of Two Integers5            BigInteger carry = x.and(y).shiftLeft(1); // columns where both are 16            x = x.xor(y);                             // add without carrying7            y = carry;8        }9        return x.toString(2);10    }11}

in the room

How to say it in the interview

talk track

Ask: may I use BigInteger or Integer.parseInt? Usually not — and parseInt overflows past 31 digits anyway.
"Two pointers from the right, a carry, a StringBuilder; reverse at the end."
Loop while i ≥ 0 or j ≥ 0 or carry > 0 — that last part writes the final 1 of 11 + 1 = 100.

traps

Integer.parseInt(a, 2): overflows past 31 digits (Long past 63), but inputs go up to 10,000.
Dropping the last carry: "1" + "1" must give "10", not "0".
sb.insert(0, digit) every column: each insert shifts the whole builder, O(n²). Append, then reverse once.
a.charAt(i) is a char: subtract '0' to get the digit 0 or 1.

what they ask next

Follow-ups

Add Two Numbers (LC 2), digits in a linked list?

The same column loop with a carry — the lists already store the digits right to left, so no reverse is needed.

Multiply two binary strings?

Schoolbook multiplication like Multiply Strings: digit i × digit j lands in column i + j; carry in base 2 instead of base 10.

before you submit

Edge cases to test

"0" + "0" → "0".
A carry runs through every digit: "1111" + "1" → "10000".
Different lengths: "1" + "111" → "1000".
10,000-digit inputs: far too big for any int or long.

practise next