Add Binary

Difficulty: Easy Source: NeetCode

Problem

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"

Constraints:

• 1 <= a.length, b.length <= 10⁴
• a and b consist only of '0' or '1' characters.
• Neither string contains leading zeros except for the string "0" itself.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary arithmetic — how carry works when adding binary digits
• String manipulation — processing characters from right to left, building a result string
• ord() and int() — converting characters to integer values in Python

1. Brute Force (Integer Conversion)

Intuition

Python can convert binary strings to integers with int(s, 2) and convert integers back to binary strings with bin(n). So the “brute force” here is barely any work at all — just let Python do the arithmetic. The trick is stripping the '0b' prefix that bin() adds.

This is completely valid for interviews if the problem allows it, but interviewers sometimes explicitly ask you to avoid built-in conversion — that’s when the next approach matters.

Algorithm

1. Convert a to an integer using int(a, 2).
2. Convert b to an integer using int(b, 2).
3. Add them.
4. Convert the result back to binary with bin(), then strip the '0b' prefix.

Solution

def addBinary(a, b):
    return bin(int(a, 2) + int(b, 2))[2:]


print(addBinary("11", "1"))      # "100"
print(addBinary("1010", "1011")) # "10101"
print(addBinary("0", "0"))       # "0"

Complexity

• Time: O(n + m) — converting and adding strings of length n and m
• Space: O(max(n, m)) — for the result string

2. Bit-by-Bit Addition with Carry

Intuition

This is how you’d add two binary numbers by hand — just like decimal addition, but simpler since each digit is only 0 or 1.

Start from the rightmost (least significant) bit of both strings and work left. At each position, add the two bits plus any carry from the previous step. The possible sums are 0, 1, 2, or 3:

• Sum 0 → digit 0, carry 0
• Sum 1 → digit 1, carry 0
• Sum 2 → digit 0, carry 1
• Sum 3 → digit 1, carry 1

In general: digit = sum % 2, carry = sum // 2.

After processing both strings, if there’s still a carry left, prepend a 1.

For "11" + "1":

position 0 (rightmost): 1 + 1 + carry(0) = 2  →  digit=0, carry=1
position 1:             1 + 0 + carry(1) = 2  →  digit=0, carry=1
no more digits, carry=1 →  prepend 1
result (reversed): "100"

Algorithm

1. Initialize pointers i = len(a) - 1, j = len(b) - 1, carry = 0, and result = [].
2. While i >= 0 or j >= 0 or carry:
   • Add int(a[i]) if i >= 0, else 0.
   • Add int(b[j]) if j >= 0, else 0.
   • Add carry.
   • Append total % 2 as a string character to result.
   • Set carry = total // 2.
   • Decrement i and j.
3. Reverse result and join into a string.

Solution

def addBinary(a, b):
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    result = []

    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
        result.append(str(total % 2))
        carry = total // 2

    return ''.join(reversed(result))


print(addBinary("11", "1"))      # "100"
print(addBinary("1010", "1011")) # "10101"
print(addBinary("0", "0"))       # "0"
print(addBinary("1111", "1111")) # "11110"

Complexity

• Time: O(max(n, m)) — one pass through both strings
• Space: O(max(n, m)) — for the result list

Common Pitfalls

Forgetting the final carry. After both strings are exhausted, there may still be a carry of 1 that needs to become a leading 1 in the result. Always keep the loop running while carry is nonzero.

Building the result in reverse. Since we process from right to left, digits are appended in reverse order. Reversing at the end (or using append + reversed) is necessary.

Using ord(c) - ord('0') vs int(c). Both work for single binary digits. int('1') == 1 is clean and readable. ord('1') - ord('0') == 1 is the same value, just more explicit about the character arithmetic.