## Question

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.

## Algorithm

Easy question but you need to find some pattern here.

For each digit you do the math you will get result number 0, 1, 2, 3.

0 is all digit is 0 and no carry from previous adding;

1 and 2 is some intermediate result ;

3 is Both number from two string is 1 and we have a carry digit.

For a specific digit, the final number is the previous result module 2 and the carry is the previous result divide 2. This is actually the process of decimal turn to binary.

## Code

class Solution { public String addBinary(String a, String b) { String res = ""; int i = a.length() - 1, j = b.length() - 1; int carry = 0; while (i >= 0 && j >= 0) { int ia = a.charAt(i) - '0'; int ib = b.charAt(j) - '0'; int cur = (ia + ib + carry) % 2; carry = (ia + ib + carry) / 2; res = String.valueOf(cur) + res; i--; j--; } while (i < 0 && j >= 0) { int ib = b.charAt(j) - '0'; int cur = (ib + carry) % 2; carry = (ib + carry) / 2; res = String.valueOf(cur) + res; j--; } while (j < 0 && i >= 0) { int ia = a.charAt(i) - '0'; int cur = (ia + carry) % 2; carry = (ia + carry) / 2; res = String.valueOf(cur) + res; i--; } if (carry == 1) { res = "1" + res; } return res; } }