LeetCode 67: Add Binary Solution in Python Explained

Problem Statement

LeetCode 67, Add Binary, is an easy-level problem where you’re given two binary strings a and b. Your task is to return their sum as a binary string. The inputs are strings of '0' and '1' characters, representing non-negative binary integers, and you must perform the addition without converting them directly to integers unless explicitly allowed as an alternative.

Constraints

1 <= a.length, b.length <= 10^4: String lengths are between 1 and 10,000.
a and b consist only of '0' or '1' characters.
No leading zeros in the input strings (except for "0" itself).

Example

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

Input: a = "1010", b = "1011"
Output: "10101"
Explanation: 1010 (10) + 1011 (11) = 10101 (21) in binary.

Input: a = "0", b = "0"
Output: "0"
Explanation: 0 + 0 = 0 in binary.

Understanding the Problem

How do you solve LeetCode 67: Add Binary in Python? For a = "11" and b = "1", compute their binary sum to get "100". We need to add two binary numbers digit-by-digit from right to left, handling carries, similar to decimal addition but in base-2. We’ll explore two approaches: an Iterative Bit-by-Bit Addition Solution (optimal and primary) and an Alternative with Integer Conversion (simpler but less aligned with the problem’s intent). The bit-by-bit method runs in O(max(n,m)) time with O(1) space, where (n) and (m) are the lengths of the strings.

Solution 1: Iterative Bit-by-Bit Addition Approach (Primary)

Explanation

Add the binary strings from right to left, keeping track of a carry. For each position, sum the digits from both strings (if available) plus the carry, append the least significant bit to the result, and update the carry. Reverse the result at the end since we build it backwards.

Here’s a flow for "1010" + "1011":

Pos 3: 0+1+0 = 1, result="1", carry=0
Pos 2: 1+1+0 = 2, result="01", carry=1
Pos 1: 0+0+1 = 1, result="101", carry=0
Pos 0: 1+1+0 = 2, result="0101", carry=1
Carry=1, result="10101"
Reverse: "10101"

Initialize Variables.

Start from right ends, carry = 0, result list.

Process Digits.

Sum digits + carry, append bit, update carry.

Handle Remaining Carry.

Append carry if non-zero.

Reverse and Join.

Convert result list to string.

Return Result.

Step-by-Step Example

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

We need "100".

Goal: Add "11" and "1" in binary.
Result for Reference: "100".
Start: a = "11", b = "1", i = 1, j = 0, carry = 0, result = [].
Step 1: i = 1, j = 0.

a[1] = '1', b[0] = '1', sum = 1 + 1 + 0 = 2.
result.append('0'), carry = 1.

Step 2: i = 0, j < 0.

a[0] = '1', sum = 1 + 0 + 1 = 2.
result.append('0'), carry = 1.

Step 3: i < 0, j < 0, carry = 1.

result.append('1'), carry = 0.

Step 4: result = ['1','0','0'], reverse and join -> "100".
Finish: Return "100".

Example 2: a = "1010", b = "1011"

We need "10101".

Start: i = 3, j = 3, carry = 0, result = [].
Step 1: i = 3, j = 3.

'0' + '1' + 0 = 1, result = ['1'], carry = 0.

Step 2: i = 2, j = 2.

'1' + '1' + 0 = 2, result = ['1','0'], carry = 1.

Step 3: i = 1, j = 1.

'0' + '0' + 1 = 1, result = ['1','0','1'], carry = 0.

Step 4: i = 0, j = 0.

'1' + '1' + 0 = 2, result = ['1','0','1','0'], carry = 1.

Step 5: carry = 1, result = ['1','0','1','0','1'].
Step 6: Reverse and join -> "10101".
Finish: Return "10101".

How the Code Works (Iterative Bit-by-Bit Addition)

Here’s the Python code with line-by-line explanation:

def addBinary(a: str, b: str) -> str:
    # Line 1: Initialize pointers and variables
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    result = []

    # Line 2: Process digits from right to left
    while i >= 0 or j >= 0 or carry:
        # Line 3: Get digits or 0 if out of bounds
        x = int(a[i]) if i >= 0 else 0
        y = int(b[j]) if j >= 0 else 0

        # Line 4: Compute sum and new carry
        total = x + y + carry
        result.append(str(total % 2))
        carry = total // 2

        # Line 5: Move pointers
        i -= 1
        j -= 1

    # Line 6: Reverse and join result
    return ''.join(result[::-1])

Alternative: Integer Conversion Approach

Explanation

Convert the binary strings to integers using base-2, add them, and convert the sum back to a binary string. This is straightforward but assumes the numbers fit within Python’s integer limits (not a concern within constraints) and uses extra space for conversion.

Convert to Integers.

Use int(str, 2) for base-2 conversion.

Add Integers.
Convert Back.

Use bin() and strip "0b" prefix.

Return Result.

Step-by-Step Example (Alternative)

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

Start: a = "1010", b = "1011".
Step 1: Convert to integers.

int("1010", 2) = 10, int("1011", 2) = 11.

Step 2: Add.

10 + 11 = 21.

Step 3: Convert back.

bin(21) = "0b10101", strip "0b" -> "10101".

Finish: Return "10101".

How the Code Works (Integer Conversion)

def addBinaryInt(a: str, b: str) -> str:
    # Line 1: Convert binary strings to integers
    num_a = int(a, 2)
    num_b = int(b, 2)

    # Line 2: Add integers
    total = num_a + num_b

    # Line 3: Convert sum back to binary string
    return bin(total)[2:]

Complexity

Iterative Bit-by-Bit Addition:

Time: O(max(n,m)) – Process longer string length.
Space: O(max(n,m)) – Result list.

Integer Conversion:

Time: O(n + m) – Conversion and addition.
Space: O(max(n,m)) – Output string.

Efficiency Notes

Iterative Bit-by-Bit Addition is O(max(n,m)) time and O(max(n,m)) space (for output), optimal for LeetCode 67 as it avoids integer conversion overhead. Integer Conversion is also O(n + m) time but relies on Python’s built-in functions, potentially less efficient for very large strings outside constraints, with similar space usage.

Key Insights

Tips to master LeetCode 67:

Bit-by-Bit: Add digits like manual binary addition.
Carry Logic: Track and propagate carry efficiently.
Reverse Build: Handle result construction from right.

Additional Example

For a = "110", b = "11":

Goal: "1001".
Bit-by-Bit: 0+1=1, 1+1=2 (0, carry=1), 1+1=2 (0, carry=1), 1 -> "1001".
Result: "1001".

Edge Cases

Single Digit: "1" + "1" – Return "10".
Different Lengths: "1" + "111" – Return "1000".
All Zeros: "0" + "0" – Return "0".

Final Thoughts

The Iterative Bit-by-Bit Addition solution is a great fit for LeetCode 67 in Python—direct, efficient, and true to binary arithmetic. For a related challenge, try LeetCode 66: Plus One to handle decimal digits! Ready to add binaries? Solve LeetCode 67 on LeetCode now and test it with "11" + "1" or "1010" + "1011" to master binary addition. Dive in and sum those bits!