Add Binary

Difficulty: Easy | Acceptance: 58.00% | Paid: No Topics: Math, String, Bit Manipulation, Simulation

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

• Examples
• Constraints
• Approach 1: Bit-by-Bit Simulation
• Approach 2: Built-in Conversion
• Approach 3: Bit Manipulation

Examples

Example 1

Input: a = "11", b = "1"
Output: "100"
Explanation: 11 + 1 = 100 in binary.

Example 2

Input: a = "1010", b = "1011"
Output: "10101"
Explanation: 1010 + 1011 = 10101 in binary.

Constraints

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

Bit-by-Bit Simulation

Intuition Simulate the elementary addition process by adding bits from the end of both strings, keeping track of the carry, just like adding numbers on paper.

Steps

• Initialize two pointers at the end of strings a and b, and a carry variable set to 0.
• Loop while at least one pointer is valid or carry is not 0.
• Calculate the sum of the current bits and the carry.
• Append the result bit (sum % 2) to the result string.
• Update the carry (sum / 2).
• Reverse the result string at the end to get the correct order.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        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))

Complexity

• Time: O(max(N, M)) where N and M are lengths of strings.
• Space: O(max(N, M)) to store the result.
• Notes: This is the most robust approach as it handles arbitrarily large inputs without overflow.

Built-in Conversion

Intuition Convert the binary strings to integers, perform standard addition, and convert the result back to a binary string.

Steps

• Parse string a to an integer.
• Parse string b to an integer.
• Add the two integers.
• Convert the sum back to a binary string.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

Complexity

• Time: O(N) for conversion and addition.
• Space: O(1) auxiliary space (excluding result storage).
• Notes: Python handles large integers automatically. Java requires BigInteger. JavaScript requires BigInt. C++ standard types are limited to 64 bits.

Bit Manipulation

Intuition Use bitwise XOR to find the sum without carry, and bitwise AND followed by a left shift to find the carry. Repeat until the carry is 0.

Steps

• Convert inputs to integers (or BigInts).
• Loop while the second number (carry) is not 0.
• Calculate carry as (a & b) << 1.
• Calculate sum without carry as a ^ b.
• Update a with the sum and b with the carry.
• Convert the final result to a binary string.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            carry = x & y
            x = x ^ y
            y = carry << 1
        return bin(x)[2:]

Complexity

• Time: O(1) for fixed-width integers, O(N) for arbitrary precision integers (like Python/Java BigInteger).
• Space: O(1) auxiliary space.
• Notes: This mimics hardware logic. For languages without BigInt, it is limited by integer size.