# 67. Add Binary

# 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 <= 10`

^{4}`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]
```