We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Add Binary

Difficulty: Easy

Problem Description

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

Key Insights

  • Binary addition is similar to decimal addition, where we add digits from right to left and carry over any value greater than 1.
  • We need to handle cases where the strings are of unequal length by padding the shorter string with leading zeros.
  • The result should be constructed in reverse order since we process from the least significant bit to the most significant bit.

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 result.

Solution

To solve this problem, we will use a two-pointer technique to traverse both binary strings from the least significant digit to the most significant digit. We will maintain a carry variable to account for any overflow during the addition. The result will be built as a string in reverse order, which we will reverse at the end before returning.

  1. Initialize pointers for both strings starting from the end (least significant bit).
  2. Initialize a carry variable to 0.
  3. Loop until both pointers are exhausted and no carry remains:
    • Add the corresponding bits from both strings and the carry.
    • Store the result bit (sum % 2) and update the carry (sum // 2).
  4. Reverse the result string before returning.

Code Solutions

def addBinary(a: str, b: str) -> str:
    result = []
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    
    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))  # Append the result bit
        carry = total // 2  # Update carry
    
    return ''.join(reversed(result))  # Reverse the result
← Back to All Questions