💬 Discord
Sign In
NeetCode #855LC-67EasyBit ManipulationNC 250
← Back to All Problems

#855 · #67 · Add Binary(二进制求和)

📌 Problem Statement & Constraints

Given two binary strings a and b, return their sum as a binary string. Constraints: 1 <= a.length, b.length <= 10^4, and each string consists only of the characters 0 and 1.

💡 Core Algorithmic Approaches

  1. Simulate schoolbook addition from the least significant end with two pointers and a carry.
  2. At each column, add the two bits (when present) and the incoming carry, emit total & 1, and set the new carry to total >> 1.
  3. Continue while either pointer is still valid or a carry remains, so the final carry of 1 + 1 is not dropped.
  4. Append digits to a list and reverse at the end, because prepending to a string is quadratic.

💻 Benchmark Python3 Implementation

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        out = []
        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
            out.append(str(total & 1))  # bit to keep
            carry = total >> 1          # carry into the next column
        return "".join(reversed(out))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(max(m, n)): one step per column.
💾 Space Complexity
O(max(m, n)): the output list.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the trailing carry: 1 + 1 produces 10, so the loop must keep going while carry is set.
  • Prepending to a string with s = ch + s: O(n^2) for inputs up to 10^4 characters; append and reverse instead.
  • Converting to int and using bin: it hides the carry logic the problem tests and is awkward for 10^4-bit strings.
  • Assuming equal lengths: the two pointers must stop independently, otherwise an index error or a wrong column alignment occurs.