LeetCode Solutions Blog

Add Binary

Number: 67

Difficulty: Easy

Paid? No

Problem Description

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

Key Insights

Simulate binary addition just like you add numbers digit by digit.
Process the strings from right to left, handling the carry at each step.
Use modulo and division operations to extract the current digit and update the carry.
Append any remaining carry at the end.

Space and Time Complexity

Time Complexity: O(max(n, m)), where n and m are the lengths of the two binary strings.
Space Complexity: O(max(n, m)) for storing the resulting binary string.

Solution

The strategy is to iterate over the input strings from the end to the beginning. At each step, calculate the sum of corresponding bits and the existing carry. Use the modulo operation (% 2) to determine the current digit and integer division (// 2) to update the carry. Once all digits have been processed, reverse the result to obtain the final binary string.

Code Solutions

# Function to add two binary strings
def addBinary(a: str, b: str) -> str:
    i = len(a) - 1  # Pointer for string a
    j = len(b) - 1  # Pointer for string b
    carry = 0  # Initialize carry to 0
    result = []  # List to store binary digits
    
    # Loop until both strings are processed and no carry remains
    while i >= 0 or j >= 0 or carry:
        total_sum = carry  # Start with the carry from previous step
        
        if i >= 0:  # If there is a digit left in a
            total_sum += int(a[i])  # Convert character to integer and add
            i -= 1  # Move to the next digit
        if j >= 0:  # If there is a digit left in b
            total_sum += int(b[j])  # Convert character to integer and add
            j -= 1  # Move to the next digit
        
        # Append the remainder of total_sum divided by 2 (0 or 1)
        result.append(str(total_sum % 2))
        carry = total_sum // 2  # Update the carry
        
    # Reverse the result since we built it backwards and join to form a string
    return ''.join(result[::-1])

# Sample test cases
print(addBinary("11", "1"))    # Expected output: "100"
print(addBinary("1010", "1011"))  # Expected output: "10101"