Problem statement

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

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= a.length, b.length <= 24
• a and b consist only of '0' or '1' characters.

Hints for Add Binary

1. Hint 1

   Do not convert to a number — the inputs can be longer than any built-in integer.

2. Hint 2

   Walk both strings from the right with a carry, exactly as you would add on paper.

3. Hint 3

   Keep looping while either string has digits left or the carry is still 1.

How to solve Add Binary

Add column by column from the right with a carry, exactly like pencil-and-paper addition, so the inputs can be arbitrarily long.

Approach

1. Point i and j at the last characters of a and b; set carry = 0.
2. While either index is valid or carry is set: sum the carry and the available bits, append sum % 2, set carry = sum // 2.
3. Reverse the collected bits and join.

Why it works

Every column sum is 0–3; its low bit is the output digit and its high bit is the carry into the next column. Continuing while the carry is set handles a result one digit longer than either input.

Complexity

• Time — O(max(len a, len b))
• Space — O(max(len a, len b))

Pitfalls

• Parsing to an integer overflows once the strings exceed 63 bits.
• Stopping when both indices run out drops the final carry — "1" + "1" must give "10".

Reference solution

Python

def addBinary(a: str, b: str) -> str:
    i, j, carry = len(a) - 1, len(b) - 1, 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 % 2))
        carry = total // 2
    return "".join(reversed(out))

Java

public static String addBinary(String a, String b) {
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    StringBuilder sb = new StringBuilder();
    while (i >= 0 || j >= 0 || carry > 0) {
        int total = carry;
        if (i >= 0) { total += a.charAt(i) - '0'; i--; }
        if (j >= 0) { total += b.charAt(j) - '0'; j--; }
        sb.append((char) ('0' + total % 2));
        carry = total > 1 ? 1 : 0;
    }
    return sb.reverse().toString();
}

C++

string addBinary(string a, string b) {
    int i = (int) a.size() - 1, j = (int) b.size() - 1, carry = 0;
    string out = "";
    while (i >= 0 || j >= 0 || carry > 0) {
        int total = carry;
        if (i >= 0) { total += a[i] - '0'; i--; }
        if (j >= 0) { total += b[j] - '0'; j--; }
        out += (char) ('0' + total % 2);
        carry = total > 1 ? 1 : 0;
    }
    reverse(out.begin(), out.end());
    return out;
}

JavaScript

var addBinary = function(a, b) {
    let i = a.length - 1, j = b.length - 1, carry = 0, out = "";
    while (i >= 0 || j >= 0 || carry > 0) {
        let total = carry;
        if (i >= 0) { total += a.charCodeAt(i) - 48; i--; }
        if (j >= 0) { total += b.charCodeAt(j) - 48; j--; }
        out = String(total % 2) + out;
        carry = total > 1 ? 1 : 0;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy