> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/math/67add-binary.md).

# 67\_Add Binary

\[easy] \[string, math]

Given two binary strings, return their sum (also a binary string). The input strings are both **non-empty** and contains only characters`1`or `0`.

**Example 1:**

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

**Example 2:**

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

## Solution 1: loop from right to left iteratively

```python
def addBinary(a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    m = len(a) - 1
    n = len(b) - 1
    ret = ''
    count = 0
    while m >= 0 or n >= 0:
        if m < 0:
            temp = int(b[n]) + count
        elif n < 0:
            temp = int(a[m]) + count
        else:
            temp = int(a[m]) + int(b[n]) + count
        if temp >= 2:
            ret = str(temp - 2) + ret
            count = 1
        else:
            ret = str(temp) + ret
            count = 0
        m -= 1
        n -= 1
    if count == 1:
        ret = str(count) + ret
    return ret
```

## Solution 2: recursively

```python
def addBinary(a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    if len(a) == 0:
        return b
    if len(b) == 0:
        return a
    if a[-1] == "1" and b[-1] == "1":
        return self.addBinary(self.addBinary(a[:-1],b[:-1]),'1') + '0'
    if a[-1] == '0' and b[-1] == "0":
        return self.addBinary(a[:-1],b[:-1])+'0'
    else:
        return self.addBinary(a[:-1],b[:-1])+'1'
```