Skip to main content
CodePeetCodePeet
CodePeet 250

Add Binary

EASYProblemSolveExternal Links

Description

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

A binary string is composed entirely of the characters '0' and '1'. Each character represents a single binary digit (bit). The rightmost bit is the least significant bit (worth 2⁰ = 1), and each bit to its left is worth twice as much — exactly like how digits in a decimal number represent ones, tens, hundreds, and so on.

Your task is to add the two binary numbers represented by these strings and return the resulting sum, also as a binary string, with no unnecessary leading zeros.

Examples

Example 1

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

Output: "100"

Explanation: The binary string "11" represents the decimal value 3 (1×2¹ + 1×2⁰ = 2 + 1 = 3). The binary string "1" represents decimal 1 (1×2⁰ = 1). Their sum is 3 + 1 = 4, which in binary is "100" (1×2² = 4). Notice the result is one character longer than either input — this happens because the addition produced a carry that created a new most-significant bit.

Example 2

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

Output: "10101"

Explanation: The binary string "1010" represents decimal 10 (1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 8 + 0 + 2 + 0 = 10). The binary string "1011" represents decimal 11 (8 + 0 + 2 + 1 = 11). Their sum is 10 + 11 = 21, which in binary is "10101" (16 + 0 + 4 + 0 + 1 = 21). This example demonstrates carry propagation through multiple bit positions.

Example 3

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

Output: "0"

Explanation: Both strings represent zero. Adding 0 + 0 = 0, so the result is simply "0". This is the simplest boundary case.

Constraints

  • 1 ≤ a.length, b.length ≤ 10^4
  • a and b consist only of '0' or '1' characters
  • Each string does not contain leading zeros except for the zero itself ("0")

Editorial

Brute Force

Intuition

The simplest way to add two binary numbers is to sidestep binary arithmetic entirely: convert both binary strings into their decimal (base-10) integer equivalents, perform ordinary addition on those integers, and then convert the result back to a binary string.

This mirrors how you might solve the problem in your head. If someone asked you "what is binary 11 plus binary 1?", you would likely think: "11 in binary is 3, 1 in binary is 1, 3 plus 1 is 4, and 4 in binary is 100." We are doing exactly that, but letting the programming language handle the conversions.

Most languages provide built-in functions or classes for base conversion. Python has int(string, 2) and bin(). Java has BigInteger with radix constructors. C++ can manually convert using arithmetic. We leverage these tools to avoid implementing binary addition logic ourselves.

Step-by-Step Explanation

Let's trace through with a = "11", b = "1":

Step 1: Convert string a to its decimal integer value.

  • a = "11"
  • Process each bit from left to right: start with 0, then for each character multiply by 2 and add the bit.
  • 0 × 2 + 1 = 1
  • 1 × 2 + 1 = 3
  • decimal_a = 3

Step 2: Convert string b to its decimal integer value.

  • b = "1"
  • 0 × 2 + 1 = 1
  • decimal_b = 1

Step 3: Perform standard integer addition.

  • sum = decimal_a + decimal_b = 3 + 1 = 4

Step 4: Convert the decimal sum back to a binary string.

  • 4 ÷ 2 = 2, remainder 0
  • 2 ÷ 2 = 1, remainder 0
  • 1 ÷ 2 = 0, remainder 1
  • Reading remainders bottom-to-top gives: "100"

Step 5: Return "100".

State tracking summary:

  • After Step 1: decimal_a = 3
  • After Step 2: decimal_b = 1
  • After Step 3: sum = 4
  • After Step 4: binary_result = "100"

The approach is straightforward — three conversions and one addition. However, the conversion step hides a critical limitation we will discuss next.

Algorithm

  1. Convert binary string a to a decimal integer (using base-2 parsing)
  2. Convert binary string b to a decimal integer
  3. Compute the sum of the two integers
  4. Convert the sum back to a binary string
  5. Return the resulting binary string

Code

class Solution {
public:
    string addBinary(string a, string b) {
        // Convert binary string to decimal (works only for strings up to 63 chars)
        long long numA = 0, numB = 0;
        for (char c : a) numA = numA * 2 + (c - '0');
        for (char c : b) numB = numB * 2 + (c - '0');
        
        long long sum = numA + numB;
        
        if (sum == 0) return "0";
        
        // Convert decimal back to binary
        string result;
        while (sum > 0) {
            result = char('0' + sum % 2) + result;
            sum /= 2;
        }
        
        return result;
    }
};
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # Python handles arbitrarily large integers natively
        decimal_a = int(a, 2)
        decimal_b = int(b, 2)
        total = decimal_a + decimal_b
        # bin() returns '0b...' prefix, so slice from index 2
        return bin(total)[2:]
import java.math.BigInteger;

class Solution {
    public String addBinary(String a, String b) {
        // BigInteger handles arbitrarily large binary numbers
        BigInteger numA = new BigInteger(a, 2);
        BigInteger numB = new BigInteger(b, 2);
        BigInteger sum = numA.add(numB);
        return sum.toString(2);
    }
}

Complexity Analysis

Time Complexity: O(n + m)

Converting binary string a (length n) to an integer requires reading each of its n characters once — O(n). Similarly, converting b (length m) takes O(m). The integer addition takes O(max(n, m)) time. Converting the sum back to binary takes O(max(n, m)) time since the result has at most max(n, m) + 1 bits. Overall: O(n + m).

Space Complexity: O(max(n, m))

The result string occupies at most max(n, m) + 1 characters. In languages with arbitrary-precision integers (Python, Java BigInteger), the intermediate integer values also use O(max(n, m)) bits of storage. In C++ with long long, intermediate storage is O(1) but the approach only works for strings up to 63 characters.

Why This Approach Is Not Efficient

Although this approach shares the same O(n + m) time complexity as the optimal solution, it has a critical practical limitation: integer overflow.

The problem allows binary strings up to 10,000 characters long. A 10,000-bit binary number is astronomically large — far beyond what standard fixed-size integer types can hold:

  • A C++ long long is 64 bits — it overflows for any binary string longer than 63 characters
  • A Java long has the same 64-bit limit
  • A 10,000-bit number has roughly 3,010 decimal digits, requiring arbitrary-precision libraries

The C++ brute force code above silently produces wrong results for inputs exceeding 63 bits. Java's BigInteger and Python's native integers handle arbitrary sizes, but they carry internal overhead for each arithmetic operation on large numbers.

Beyond overflow, this approach is conceptually wasteful: we convert from binary to decimal, add in decimal, then convert back to binary. Binary addition can be performed directly on the string representation — one bit at a time — without ever leaving the binary domain. This direct approach works for any input length, in every language, with no risk of overflow.

Optimal Approach - Bit-by-Bit Addition with Carry

Intuition

Think about how you add two multi-digit decimal numbers on paper: you start from the rightmost column, add the digits in that column along with any carry from the previous column, write down the result digit, and pass any carry to the next column to the left.

Binary addition works exactly the same way, but the arithmetic is simpler because each digit can only be 0 or 1. The complete rules for adding a single column of binary digits are:

  • 0 + 0 + 0 (no carry) = 0, carry out 0
  • 0 + 1 + 0 = 1, carry out 0
  • 1 + 0 + 0 = 1, carry out 0
  • 1 + 1 + 0 = 0, carry out 1 (because 2 in binary is "10")
  • 0 + 0 + 1 (carry in) = 1, carry out 0
  • 0 + 1 + 1 = 0, carry out 1
  • 1 + 0 + 1 = 0, carry out 1
  • 1 + 1 + 1 = 1, carry out 1 (because 3 in binary is "11")

Notice the elegant pattern: for any column sum s, the result bit is s % 2 (the remainder when divided by 2) and the carry out is s / 2 (integer division by 2). This single formula handles all cases.

We use two pointers starting at the last character of each string and move them leftward in lockstep. A carry variable acts as our "memory" from one column to the next. When both strings are exhausted, if a carry remains, it becomes the leading bit of the result.

Step-by-Step Explanation

Let's trace through with a = "1010", b = "1011":

Step 1: Initialize pointers at the end of each string: i = 3 (pointing to a[3] = '0'), j = 3 (pointing to b[3] = '1'). Set carry = 0 and result = "".

Step 2: Process the rightmost column (position 3).

  • Read a[3] = '0' → bit_a = 0
  • Read b[3] = '1' → bit_b = 1
  • sum = bit_a + bit_b + carry = 0 + 1 + 0 = 1
  • result_bit = 1 % 2 = 1, new carry = 1 / 2 = 0
  • Prepend '1' to result → result = "1"
  • Move pointers left: i = 2, j = 2

Step 3: Process position 2.

  • Read a[2] = '1' → bit_a = 1
  • Read b[2] = '1' → bit_b = 1
  • sum = 1 + 1 + 0 = 2
  • result_bit = 2 % 2 = 0, new carry = 2 / 2 = 1
  • Carry generated! Both bits are 1, so their sum exceeds what a single bit can hold.
  • Prepend '0' → result = "01"
  • Move pointers: i = 1, j = 1

Step 4: Process position 1.

  • Read a[1] = '0' → bit_a = 0
  • Read b[1] = '0' → bit_b = 0
  • sum = 0 + 0 + 1 (carry from step 3) = 1
  • result_bit = 1 % 2 = 1, new carry = 1 / 2 = 0
  • The incoming carry is consumed. Prepend '1' → result = "101"
  • Move pointers: i = 0, j = 0

Step 5: Process position 0 (the leftmost bits).

  • Read a[0] = '1' → bit_a = 1
  • Read b[0] = '1' → bit_b = 1
  • sum = 1 + 1 + 0 = 2
  • result_bit = 2 % 2 = 0, new carry = 2 / 2 = 1
  • Another carry generated! Prepend '0' → result = "0101"
  • Both pointers exhausted: i = -1, j = -1

Step 6: Both strings are fully processed, but carry = 1 still remains.

  • Prepend '1' → result = "10101"
  • Carry resolved.

Step 7: Return "10101".

Bit-by-Bit Binary Addition — Right to Left with Carry — The top row shows string a, the middle row shows string b, and the bottom row shows the result being built from right to left. Watch how the carry propagates between columns.

Algorithm

  1. Set pointer i to the last index of string a, and pointer j to the last index of string b
  2. Initialize carry = 0 and an empty result container
  3. While i ≥ 0 OR j ≥ 0 OR carry > 0:
    • Read bit_a: if i ≥ 0, it is a[i] - '0'; otherwise 0
    • Read bit_b: if j ≥ 0, it is b[j] - '0'; otherwise 0
    • Compute sum = bit_a + bit_b + carry
    • The result bit for this column is sum % 2
    • The new carry is sum / 2
    • Prepend (or append and later reverse) the result bit to the output
    • Decrement both i and j
  4. Return the result string

Code

class Solution {
public:
    string addBinary(string a, string b) {
        string result;
        int carry = 0;
        int i = a.size() - 1;
        int j = b.size() - 1;
        
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            result = char('0' + sum % 2) + result;
            carry = sum / 2;
        }
        
        return result;
    }
};
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        carry = 0
        i = len(a) - 1
        j = len(b) - 1
        
        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))
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;
        
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            result.append(sum % 2);
            carry = sum / 2;
        }
        
        return result.reverse().toString();
    }
}

Complexity Analysis

Time Complexity: O(max(n, m))

We iterate through both strings simultaneously from right to left. The loop runs for max(n, m) iterations (where n = length of a, m = length of b), plus at most one additional iteration to handle a final carry. In each iteration, we perform a constant amount of work: reading at most two characters, computing one addition, one modulo, and one division — all O(1) operations. Total: O(max(n, m)).

Space Complexity: O(max(n, m))

The result string has at most max(n, m) + 1 characters (the extra character accounts for a potential leading carry). Beyond the output, we use only a fixed number of integer variables (carry, sum, i, j), which is O(1) auxiliary space. If we exclude the output from the space analysis, the auxiliary space is O(1), making this approach space-optimal.

Compared to the brute force, this approach avoids creating intermediate large-integer representations and works directly on the string characters — no risk of integer overflow regardless of input length.