> For the complete documentation index, see [llms.txt](https://yyloumike.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://yyloumike.gitbook.io/leetcode/string/0067.-add-binary.md).

# 0067. Add Binary

Easy  |  String  |  28 ms (90.81%),  14.3 MB (52.55%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Add Binary](https://leetcode.com/problems/add-binary/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0067-add-binary)

Given two binary strings `a` and `b`, return *their sum as a binary string*.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**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.

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Use **two pointers** to **iterate each string from the end.**&#x20;

**Note** that need to **check whether the pointer's index** is larger than 0 or not.\
Besides, **check "Carry" value** in each iteration and the end of the program.
{% endhint %}
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        
        # ==================================================
        #  String + Math                                   =
        # ==================================================
        # time  : O(max(n,m))
        # space : O(1)
        
        ans = ''
        n1, n2, carry = len(a) - 1, len(b) - 1, 0
        
        while n1 >= 0 or n2 >= 0:
            bit1 = int(a[n1]) if n1 >= 0 else 0
            bit2 = int(b[n2]) if n2 >= 0 else 0
            
            result = bit1 + bit2 + carry
            if result > 1:
                result -= 2
                carry = 1
            else:
                carry = 0
                
            ans = str(result) + ans
            
            n1 -= 1
            n2 -= 1
            
        if carry: ans = '1' + ans
        return ans
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(max(m,n))
     * @space : O(1)
     */
    
    public String addBinary(String a, String b) {
        int n1 = a.length() - 1, n2 = b.length() - 1, carry = 0;
        StringBuilder ans = new StringBuilder();
        
        while(n1 >= 0 || n2 >= 0) {
            int bit1 = (n1 >= 0) ? a.charAt(n1) - '0' : 0;
            int bit2 = (n2 >= 0) ? b.charAt(n2) - '0' : 0;
            
            int sum = bit1 + bit2 + carry;
            if(sum > 1) {
                sum -= 2;
                carry = 1;
            } else {
                carry = 0;
            }
            
            ans.append(sum);
            
            n1--;
            n2--;
        }
        
        if(carry != 0) ans.append(carry);
        return ans.reverse().toString();
    }
}
```

{% endtab %}
{% endtabs %}