67. Add Binary - Explanation

Description

You are given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "101", b = "10"

Output: "111"

Example 2:

Input: a = "10010", b = "111"

Output: "11001"

Constraints:

1 <= a.length, b.length <= 10,000
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Iteration

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = ""
        carry = 0

        a, b = a[::-1], b[::-1]
        for i in range(max(len(a), len(b))):
            digitA = ord(a[i]) - ord("0") if i < len(a) else 0
            digitB = ord(b[i]) - ord("0") if i < len(b) else 0

            total = digitA + digitB + carry
            char = str(total % 2)
            res = char + res
            carry = total // 2

        if carry:
            res = "1" + res

        return res

Time & Space Complexity

Time complexity: $O(max(m, n))$
Space complexity: $O(m + n)$

Where $m$ and $n$ are the lengths of the strings $a$ and $b$ respectively.

2. Iteration (Optimal)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        carry = 0

        i, j = len(a) - 1, len(b) - 1
        while i >= 0 or j >= 0 or carry > 0:
            digitA = int(a[i]) if i >= 0 else 0
            digitB = int(b[j]) if j >= 0 else 0

            total = digitA + digitB + carry
            res.append(total % 2)
            carry = total // 2

            i -= 1
            j -= 1

        res.reverse()
        return ''.join(map(str, res))

Time & Space Complexity

Time complexity: $O(max(m, n))$
Space complexity: $O(max(m, n))$

Where $m$ and $n$ are the lengths of the strings $a$ and $b$ respectively.