# 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]