Add Binary

Problem Statement

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

You may assume neither string has leading zeros, except for the zero itself.

What to notice first

• Binary addition works exactly like decimal addition, just with carries at each power of 2.
• Process from right to left, tracking the carry bit just like in elementary school addition.
• The result string may be one bit longer than the inputs if there’s a final carry.

Examples

Input a	Input b	Output	Explanation
"11"	"1"	"100"	3 + 1 = 4 in binary
"1010"	"1011"	"10101"	10 + 11 = 21 in binary
"0"	"0"	"0"	Edge case: zero + zero

Constraints

• 1 <= a.length, b.length <= 10^4
• a and b consist of only '0' or '1' characters
• Each string does not have leading zeros except for the zero itself

Real-World Applications

Where this pattern appears

• Arbitrary precision arithmetic — implementing addition for numbers too large for native integer types.
• Cryptographic operations — multi-precision arithmetic in public-key algorithms.
• Quantum computing simulators — representing quantum state vectors as binary values.
• Hardware design — ALU (Arithmetic Logic Unit) simulation and validation.

Complexity Comparison

Approach	Time	Space	Notes
String Simulation	O(max(n, m))	O(max(n, m))	Manual carry propagation, easy to understand
Bit Operations	O(max(n, m))	O(max(n, m))	Convert to integers, add natively, convert back

* n = length of string a, m = length of string b

Which approach should you learn first?

• Pick String Simulation if you want to understand how binary addition works at the bit level.
• Pick Bit Operations if you want the simplest implementation using built-in radix conversion.

Most Intuitive

String Simulation

O(max(n, m)) time · O(max(n, m)) space

Simplest Code

Bit Operations

O(max(n, m)) time · O(max(n, m)) space

Approach 1: String Simulation (Recommended)

★ Recommended

Simulate elementary school binary addition: process digits from right to left, maintaining a carry bit. When you reach the end of the shorter string, pad with zeros and continue.

⏱ Time O(max(n, m)) Single pass right to left 💾 Space O(max(n, m)) Result string storage

Step-by-step Example

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

Step	i	j	a[i]	b[j]	carry	sum	Action
1	3	3	0	1	0	1	Append 1, carry=0
2	2	2	1	1	0	2	Append 0, carry=1
3	1	1	0	0	1	1	Append 1, carry=0
4	0	0	1	1	0	2	Append 0, carry=1
5	-1	-1	-	-	1	-	Append 1, done
Result: "10101"

Bit-Level Visualization

    1010     (input a)
  + 1011     (input b)
  ------

Step 1:  0 + 1 + 0 = 1, no carry
Step 2:  1 + 1 + 0 = 10 (binary) = 0 with carry 1
Step 3:  0 + 0 + 1 = 1, no carry
Step 4:  1 + 1 + 0 = 10 (binary) = 0 with carry 1
Step 5:       carry 1 left = 1

Result: 10101

Pseudocode

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

    while i >= 0 or j >= 0 or carry:
        digitA = a[i] if i >= 0 else 0
        digitB = b[j] if j >= 0 else 0
        total = digitA + digitB + carry
        result.append(total % 2)
        carry = total // 2
        i -= 1
        j -= 1

    return reverse(result).join('')

Solution Code

Python

add_binary_string_simulation.py

def add_binary_string_simulation(a: str, b: str) -> str:
    """
    String simulation approach - simulate binary addition from right to left.
    Time: O(max(len(a), len(b)))
    Space: O(max(len(a), len(b))) for result
    """
    result = []
    carry = 0
    i = len(a) - 1
    j = len(b) - 1

    while i >= 0 or j >= 0 or carry:
        digit_a = int(a[i]) if i >= 0 else 0
        digit_b = int(b[j]) if j >= 0 else 0

        total = digit_a + digit_b + carry
        result.append(str(total % 2))
        carry = total // 2

        i -= 1
        j -= 1

    return ''.join(reversed(result))


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

C++

add_binary_string_simulation.cpp

#include <string>
#include <iostream>

using namespace std;

string addBinaryStringSimulation(string a, string b) {
    /*
    String simulation approach - simulate binary addition from right to left.
    Time: O(max(a.size(), b.size()))
    Space: O(max(a.size(), b.size())) for result
    */
    string result = "";
    int carry = 0;
    int i = a.size() - 1;
    int j = b.size() - 1;

    while (i >= 0 || j >= 0 || carry) {
        int digit_a = (i >= 0) ? (a[i] - '0') : 0;
        int digit_b = (j >= 0) ? (b[j] - '0') : 0;

        int total = digit_a + digit_b + carry;
        result = char('0' + (total % 2)) + result;
        carry = total / 2;

        i--;
        j--;
    }

    return result;
}

int main() {
    cout << addBinaryStringSimulation("11", "1") << endl;      // "100"
    cout << addBinaryStringSimulation("1010", "1011") << endl; // "10101"
    cout << addBinaryStringSimulation("0", "0") << endl;       // "0"
    return 0;
}

Java

AddBinaryStringSimulation.java

public class AddBinaryStringSimulation {
    /*
    String simulation approach - simulate binary addition from right to left.
    Time: O(max(a.length(), b.length()))
    Space: O(max(a.length(), b.length())) for result
    */
    public static String addBinaryStringSimulation(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 digitA = (i >= 0) ? (a.charAt(i) - '0') : 0;
            int digitB = (j >= 0) ? (b.charAt(j) - '0') : 0;

            int total = digitA + digitB + carry;
            result.append(total % 2);
            carry = total / 2;

            i--;
            j--;
        }

        return result.reverse().toString();
    }

    public static void main(String[] args) {
        System.out.println(addBinaryStringSimulation("11", "1"));      // "100"
        System.out.println(addBinaryStringSimulation("1010", "1011")); // "10101"
        System.out.println(addBinaryStringSimulation("0", "0"));       // "0"
    }
}

JavaScript

add_binary_string_simulation.js

/**
 * String simulation approach - simulate binary addition from right to left.
 * Time: O(max(a.length, b.length))
 * Space: O(max(a.length, b.length)) for result
 */
function addBinaryStringSimulation(a, b) {
    const result = [];
    let carry = 0;
    let i = a.length - 1;
    let j = b.length - 1;

    while (i >= 0 || j >= 0 || carry) {
        const digitA = i >= 0 ? parseInt(a[i]) : 0;
        const digitB = j >= 0 ? parseInt(b[j]) : 0;

        const total = digitA + digitB + carry;
        result.push(total % 2);
        carry = Math.floor(total / 2);

        i--;
        j--;
    }

    return result.reverse().join('');
}

console.log(addBinaryStringSimulation("11", "1"));      // "100"
console.log(addBinaryStringSimulation("1010", "1011")); // "10101"
console.log(addBinaryStringSimulation("0", "0"));       // "0"

Rust

add_binary_string_simulation.rs

pub fn add_binary_string_simulation(a: String, b: String) -> String {
    /*
    String simulation approach - simulate binary addition from right to left.
    Time: O(max(a.len(), b.len()))
    Space: O(max(a.len(), b.len())) for result
    */
    let mut result = Vec::new();
    let mut carry = 0;
    let a_bytes = a.as_bytes();
    let b_bytes = b.as_bytes();
    let mut i = a_bytes.len() as i32 - 1;
    let mut j = b_bytes.len() as i32 - 1;

    while i >= 0 || j >= 0 || carry > 0 {
        let digit_a = if i >= 0 { (a_bytes[i as usize] - b'0') as i32 } else { 0 };
        let digit_b = if j >= 0 { (b_bytes[j as usize] - b'0') as i32 } else { 0 };

        let total = digit_a + digit_b + carry;
        result.push((b'0' + (total % 2) as u8) as char);
        carry = total / 2;

        i -= 1;
        j -= 1;
    }

    result.reverse();
    result.iter().collect()
}

fn main() {
    println!("{}", add_binary_string_simulation("11".to_string(), "1".to_string()));      // "100"
    println!("{}", add_binary_string_simulation("1010".to_string(), "1011".to_string())); // "10101"
    println!("{}", add_binary_string_simulation("0".to_string(), "0".to_string()));       // "0"
}

Go

add_binary_string_simulation.go

package main

import (
  "fmt"
  "strings"
)

/*
String simulation approach - simulate binary addition from right to left.
Time: O(max(len(a), len(b)))
Space: O(max(len(a), len(b))) for result
*/
func addBinaryStringSimulation(a string, b string) string {
  var result strings.Builder
  carry := 0
  i := len(a) - 1
  j := len(b) - 1

  for i >= 0 || j >= 0 || carry > 0 {
    digitA := 0
    if i >= 0 {
      digitA = int(a[i] - '0')
    }

    digitB := 0
    if j >= 0 {
      digitB = int(b[j] - '0')
    }

    total := digitA + digitB + carry
    result.WriteByte(byte('0' + (total % 2)))
    carry = total / 2

    i--
    j--
  }

  // Reverse the result
  str := result.String()
  runes := []rune(str)
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    runes[i], runes[j] = runes[j], runes[i]
  }
  return string(runes)
}

func main() {
  fmt.Println(addBinaryStringSimulation("11", "1"))      // "100"
  fmt.Println(addBinaryStringSimulation("1010", "1011")) // "10101"
  fmt.Println(addBinaryStringSimulation("0", "0"))       // "0"
}

Approach 2: Bit Operations

✓ Simple

Convert both binary strings to integers using the built-in radix parser, add them using native arithmetic, then convert the result back to binary.

This approach leverages language-native support for arbitrary precision (Python, JavaScript BigInt) or fixed-width integers with overflow-safe addition.

⏱ Time O(max(n, m)) Conversion + addition 💾 Space O(max(n, m)) Result string storage

Step-by-step Example

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

Step 1: int('11', 2) = 3
Step 2: int('1', 2) = 1
Step 3: 3 + 1 = 4
Step 4: bin(4) = '0b100'
Result: '100' (strip '0b' prefix)

Pseudocode

function addBinaryBitOperations(a, b):
    numA = parseInt(a, 2)
    numB = parseInt(b, 2)
    total = numA + numB
    return bin(total).replace('0b', '')

Solution Code

Python

add_binary_bit_operations.py

def add_binary_bit_operations(a: str, b: str) -> str:
    """
    Bit operations approach - convert to int, add, convert back to binary.
    Time: O(max(len(a), len(b)))
    Space: O(max(len(a), len(b))) for result
    """
    num_a = int(a, 2)  # Convert binary string to integer
    num_b = int(b, 2)
    total = num_a + num_b
    return bin(total)[2:]  # Convert back to binary string (remove '0b' prefix)


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

C++

add_binary_bit_operations.cpp

#include <string>
#include <iostream>

using namespace std;

string addBinaryBitOperations(string a, string b) {
    /*
    Bit operations approach - convert to long, add, convert back to binary.
    Time: O(max(a.size(), b.size()))
    Space: O(max(a.size(), b.size())) for result
    */
    long num_a = stoll(a, nullptr, 2);  // Convert binary string to long
    long num_b = stoll(b, nullptr, 2);
    long total = num_a + num_b;

    // Convert back to binary string
    if (total == 0) return "0";
    string result = "";
    while (total > 0) {
        result = char('0' + (total % 2)) + result;
        total /= 2;
    }
    return result;
}

int main() {
    cout << addBinaryBitOperations("11", "1") << endl;      // "100"
    cout << addBinaryBitOperations("1010", "1011") << endl; // "10101"
    cout << addBinaryBitOperations("0", "0") << endl;       // "0"
    return 0;
}

Java

AddBinaryBitOperations.java

public class AddBinaryBitOperations {
    /*
    Bit operations approach - convert to long, add, convert back to binary.
    Time: O(max(a.length(), b.length()))
    Space: O(max(a.length(), b.length())) for result
    */
    public static String addBinaryBitOperations(String a, String b) {
        long numA = Long.parseLong(a, 2);  // Convert binary string to long
        long numB = Long.parseLong(b, 2);
        long total = numA + numB;
        return Long.toBinaryString(total);
    }

    public static void main(String[] args) {
        System.out.println(addBinaryBitOperations("11", "1"));      // "100"
        System.out.println(addBinaryBitOperations("1010", "1011")); // "10101"
        System.out.println(addBinaryBitOperations("0", "0"));       // "0"
    }
}

JavaScript

add_binary_bit_operations.js

/**
 * Bit operations approach - convert to BigInt, add, convert back to binary.
 * Time: O(max(a.length, b.length))
 * Space: O(max(a.length, b.length)) for result
 */
function addBinaryBitOperations(a, b) {
    const numA = BigInt(a, 2);  // Can't use radix in BigInt constructor
    const numB = BigInt(b, 2);

    // Use parseInt to convert
    const totalNum = BigInt(parseInt(a, 2) + parseInt(b, 2));
    return totalNum.toString(2);
}

// Alternative simpler approach
function addBinaryBitOperationsSimple(a, b) {
    return (parseInt(a, 2) + parseInt(b, 2)).toString(2);
}

console.log(addBinaryBitOperationsSimple("11", "1"));      // "100"
console.log(addBinaryBitOperationsSimple("1010", "1011")); // "10101"
console.log(addBinaryBitOperationsSimple("0", "0"));       // "0"

Rust

add_binary_bit_operations.rs

pub fn add_binary_bit_operations(a: String, b: String) -> String {
    /*
    Bit operations approach - convert to u64, add, convert back to binary.
    Time: O(max(a.len(), b.len()))
    Space: O(max(a.len(), b.len())) for result
    */
    let num_a = u64::from_str_radix(&a, 2).unwrap();
    let num_b = u64::from_str_radix(&b, 2).unwrap();
    let total = num_a + num_b;
    format!("{:b}", total)
}

fn main() {
    println!("{}", add_binary_bit_operations("11".to_string(), "1".to_string()));      // "100"
    println!("{}", add_binary_bit_operations("1010".to_string(), "1011".to_string())); // "10101"
    println!("{}", add_binary_bit_operations("0".to_string(), "0".to_string()));       // "0"
}

Go

add_binary_bit_operations.go

package main

import (
  "fmt"
  "strconv"
)

/*
Bit operations approach - convert to uint64, add, convert back to binary.
Time: O(max(len(a), len(b)))
Space: O(max(len(a), len(b))) for result
*/
func addBinaryBitOperations(a string, b string) string {
  numA, _ := strconv.ParseUint(a, 2, 64)
  numB, _ := strconv.ParseUint(b, 2, 64)
  total := numA + numB
  return strconv.FormatUint(total, 2)
}

func main() {
  fmt.Println(addBinaryBitOperations("11", "1"))      // "100"
  fmt.Println(addBinaryBitOperations("1010", "1011")) // "10101"
  fmt.Println(addBinaryBitOperations("0", "0"))       // "0"
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

add_binary_space_optimized.py

"""
Solution for Add Binary
"""

def solve():
    """Implementation for approach 3 of Add Binary"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

add_binary_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Add Binary
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

AddBinarySpaceOptimized.java

/**
 * Solution for Add Binary
 * Approach 3
 */
public class AddBinarySpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

add_binary_space_optimized.js

/**
 * Solution for Add Binary
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

add_binary_space_optimized.rs

/// Solution for Add Binary
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

add_binary_space_optimized.go

package main

import "fmt"

// Solution for Add Binary
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Forgetting to append the final carry bit if there’s an overflow.
• Processing from left to right instead of right to left (carry won’t propagate correctly).
• Confusing the output: you’re building the result in reverse, so remember to reverse it.
• For languages with fixed-width integers (C++, Java), watch out for overflow on very large inputs.

Related Problems

• Reverse Bits ↗ Easy #190
• Number of 1 Bits ↗ Easy #191
• Add Two Numbers ↗ Medium #2
• Sum of Two Integers ↗ Medium #371

Interview Tips

Key trade-offs to discuss

• String Simulation vs. Bit Operations: String Simulation shows you understand binary arithmetic deeply; Bit Operations is faster to code in an interview but may seem like you’re “cheating” with built-in functions.
• Edge cases: Zero strings, single-bit inputs, very long inputs (10^4 characters), carry overflow.
• Follow-up: Can you implement this without converting to integers (in languages with limited integer size)? Can you do it iteratively vs. recursively?
• Why binary addition: It’s the foundation of CPU arithmetic; understanding this helps with hardware-level thinking.

Next
#190 Reverse Bits →