Domain 1EasyCORE

Add Binary

The problem requires adding two binary strings `a` and `b` and returning their sum as a binary string. The inputs are two non-empty strings consisting only of '0' or '1', with no leading zeros except for the number zero itself. The output should be a binary string representing the sum of the two input binary numbers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#String

67. Add Binary

Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 47.3%


Problem Breakdown

The problem requires adding two binary strings a and b and returning their sum as a binary string. The inputs are two non-empty strings consisting only of ‘0’ or ‘1’, with no leading zeros except for the number zero itself. The output should be a binary string representing the sum of the two input binary numbers.

Inputs:

  • Two binary strings a and b.

Outputs:

  • A single binary string representing the sum of a and b.

Implicit Constraints/Edge Cases:

  • The length of each string is between 1 and 10,000.
  • No leading zeros in the input strings except for the number zero itself.

Intuition

A brute-force approach would involve converting the binary strings to integers, performing the addition, and then converting the result back to a binary string. However, this approach is inefficient due to potential overflow issues with large numbers and unnecessary conversions.

The key insight is to simulate the manual process of binary addition by iterating from the least significant bit (rightmost) to the most significant bit (leftmost), just like how we do it manually on paper. This involves keeping track of a carry that propagates as needed during the addition.

Approach

  1. Initialize an empty list result to store the resulting binary digits.
  2. Use two pointers, i and j, initialized to the last index of strings a and b, respectively.
  3. Initialize a variable carry to 0 to keep track of the carry-over during addition.
  4. Iterate while either pointer is non-negative or there is a carry:
    • Extract the current bits from a and b if the pointers are within bounds; otherwise, use 0.
    • Calculate the sum of the two bits and the carry.
    • Append the least significant bit of the sum to the result list.
    • Update the carry to be the most significant bit of the sum.
  5. Decrement both pointers.
  6. After the loop, if there is a remaining carry, append it to the result list.
  7. Reverse the result list and join it into a string to form the final binary sum.

Complexity Analysis

  • Time Complexity: O(max(len(a), len(b))), where len(a) and len(b) are the lengths of the input strings. We iterate through each string once.
  • Space Complexity: O(max(len(a), len(b))) for storing the result list, plus a few extra variables.

Solution

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:
        bit_a = int(a[i]) if i >= 0 else 0
        bit_b = int(b[j]) if j >= 0 else 0
        total = bit_a + bit_b + carry
        result.append(str(total % 2))
        carry = total // 2
        i -= 1
        j -= 1
    
    return ''.join(result[::-1])

Edge Cases Handled

  • Empty Strings: Although the problem constraints state that the strings are non-empty, if they were empty, the function would correctly handle it by returning “0”.
  • Single Digit Inputs: The function handles cases where either or both input strings are a single digit.
  • Carry Over at the End: If there is a carry left after processing all bits, it is correctly appended to the result.