Add Two Binary Strings

Easy10–15 min

Topics

StringMath

Companies

AmazonMicrosoftGoogleFacebook

Given two binary strings a and b, return their sum, also as a binary string. This is elementary-school addition, just in base 2 instead of base 10 — walk both strings from the rightmost digit, add corresponding digits plus any carry from the previous position, and keep the overflow as a carry into the next position. The only real design decision is HOW to build the result string as you go: strings are immutable, so repeatedly gluing a new digit onto the FRONT forces a full copy every time. Appending to the end instead — then reversing once at the finish — does the same amount of real work in a fraction of the total time.

Test Case 1:

Input:a = "1010", b = "1011"

Output:"10101"

Explanation:A carry ripples through several positions before the addition finishes.

Test Case 2:

Input:a = "11", b = "1"

Output:"100"

Explanation:The final carry adds an extra digit to the result.

Test Case 3:

Input:a = "0", b = "0"

Output:"0"

Explanation:Zero plus zero is zero.

Constraints

◆1 ≤ a.length, b.length ≤ 10⁴
◆a and b consist only of the characters '0' or '1'
◆Neither a nor b has leading zeros, except the string "0" itself

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

a (binary string) — 2-8 binary digitsb (binary string) — 2-8 binary digits

1	class Solution {
2	public String addBinary(String a, String b) {
3	StringBuilder result = new StringBuilder();
4	int i = a.length() - 1, j = b.length() - 1, carry = 0;
5	while (i >= 0 \|\| j >= 0 \|\| carry > 0) {
6	int sum = carry;
7	if (i >= 0) sum += a.charAt(i--) - '0';
8	if (j >= 0) sum += b.charAt(j--) - '0';
9	result.append(sum % 2);
10	carry = sum / 2;
11	}
12	return result.reverse().toString();
13	}
14	}
15

String

↑i

String

↑j

Variables

i3

j3

carry0

INITIALIZE

Start at the rightmost digit of both strings (i = 3, j = 3), with carry = 0 and an empty buffer to append into.

Step 1 / 12

Approach & Solutions

Brute Force — Prepend to a Growing String

Brute

Walk both strings from the rightmost digit, tracking a carry. At each position, compute the digit sum and PREPEND the resulting bit to the front of the result string. Correct, but strings are immutable — every prepend allocates a brand-new string and copies everything built so far, so the total cost adds up to O(n²).

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        String result = "";
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            result = (sum % 2) + result;
            carry = sum / 2;
        }
        return result;
    }
}

Optimal — StringBuilder Append + Reverse

Optimal

Same digit-by-digit walk with a carry, but APPEND each new bit to the end of a mutable buffer instead of prepending — appending is O(1) amortized, since nothing already in the buffer needs to move. That builds the digits in reverse order, so reverse the whole buffer once at the end. One O(n) reversal is far cheaper than n prepends.

TimeO(n)