Add Binary

The problem description can be found in LeetCode.

Approach

The problem is quite simple. We just need to start from the end of the string to start calculating the first digit of the sum and then go backward to calculate all the other digits.

So, the difficult part of the problem is to avoid the index out of range exception.

Solution

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        ans = []
        carry = 0

        while i >= 0 or j >= 0:
            num1 = int(a[i]) if i >= 0 else 0
            num2 = int(b[j]) if j >= 0 else 0
            s = num1 + num2 + carry
            carry = s // 2
            ans.append(str(s % 2))

            i -= 1
            j -= 1

        if carry:
            ans.append("1")

        return "".join(reversed(ans))

Complexity

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

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