class Solution:
    def addBinary(self, a: str, b: str) -> str:

        """
        1 1 0
        1 0 1

        0 + 0 = 0
        1 + 1 = 10
        1 + 1 + 1 = 11
        """

        # add zeros at the beginning of the string
        n = max(len(a), len(b))
        a = a.zfill(n)
        b = b.zfill(n)

        result = ""

        carry = 0
        for i in range(n-1, -1, -1):
            total = carry + int(a[i]) + int(b[i])
            result = str(total%2) + result
            carry = total//2

        if carry>0:
            result = str(carry) + result

        return result