Problem

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1" Output: "100"

Example 2:

Input: a = "1010", b = "1011" Output: "10101"

Constraints:

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

Solution

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        """
        The first thing we should always do with leetcode is to define the question.
        How are binary numbers added? Let's start with a simple example.
            01
        +   10
        =   11
        Starting from left to right, we add the ones together. 1 + 0 = 1, 0 + 1 = 1
        So our result is 11. In Decimal this is 3.

        What happens when we have an overflow?
            11
        +   10
        We add 1 + 0 to 1:
            11
        +   10
        =   11
        But now we add 1 + 1. In mathematics we carry the 1 forward one decimal place and leave a 0 behind:
            11
        +   10
        =  101
        """ 

        a = list(a)
        b = list(b)
        carry = 0
        result = ''
        """
        a may be lenght 6, b may be length 4
        So we may end up with...
            111101
        +     1101
        We need to loop until we end
        """
        while a or b or carry:
            # If we have items in a, we want to add them to the carry
            if a:
                carry += int(a.pop())
            # similar for b
            if b:
                carry += int(b.pop())

            # Our result at this row is whatever the carry is modulused by 2
            """
            if the carry is 1, 1 % 2 = 1
            If our carry is 2, 2 % 2 = 0 so we can insert a 0 into that place and move onto the next
            """
            result += str(carry % 2)
            # We floor divide carry by 2 to remove the carry after we're done
            carry //= 2
        return result[::-1]