# LeetCode 67: Add Binary

## Problem Restatement

We are given two binary strings, `a` and `b`.

Each string contains only characters `"0"` and `"1"`.

We need to return their sum as a binary string.

The official constraints are `1 <= a.length, b.length <= 10^4`, both strings contain only binary digits, and neither string has leading zeroes except the string `"0"` itself.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two binary strings `a` and `b` |
| Output | Their sum as a binary string |
| Characters | Only `"0"` and `"1"` |
| Leading zeroes | Not present except for `"0"` |

Function shape:

```python
def addBinary(a: str, b: str) -> str:
    ...
```

## Examples

For:

```python
a = "11"
b = "1"
```

`"11"` is binary for `3`.

`"1"` is binary for `1`.

Their sum is `4`, which is:

```python
"100"
```

So the answer is:

```python
"100"
```

For:

```python
a = "1010"
b = "1011"
```

These represent:

```text
1010 = 10
1011 = 11
```

Their sum is `21`, which is:

```python
"10101"
```

So the answer is:

```python
"10101"
```

## First Thought: Convert to Integers

In Python, we could write:

```python
return bin(int(a, 2) + int(b, 2))[2:]
```

This is short and works in Python.

But the problem is meant to test manual binary addition. In many languages, the binary strings may be too long for normal integer types.

So we should add the strings directly.

## Key Insight

Binary addition works like decimal addition, but each digit is base `2`.

We add from right to left.

At each step, we add:

1. The current bit from `a`
2. The current bit from `b`
3. The carry from the previous step

The result bit is:

```python
total % 2
```

The next carry is:

```python
total // 2
```

For example:

| `a` bit | `b` bit | Carry in | Total | Result bit | Carry out |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 2 | 0 | 1 |
| 1 | 1 | 1 | 3 | 1 | 1 |

## Algorithm

Use two pointers:

```python
i = len(a) - 1
j = len(b) - 1
```

Use a carry:

```python
carry = 0
```

Use a list to collect result bits in reverse order:

```python
ans = []
```

While there is still work to do:

```python
while i >= 0 or j >= 0 or carry:
```

1. Start with `carry`.
2. Add `a[i]` if `i` is valid.
3. Add `b[j]` if `j` is valid.
4. Append `total % 2`.
5. Set `carry = total // 2`.
6. Move both pointers left.

At the end, reverse the collected bits and join them.

## Correctness

The algorithm processes bits from least significant to most significant, which is the standard order for addition with carry.

At each position, `total` is exactly the sum of the two input bits at that position plus the carry from all lower positions. The algorithm writes `total % 2`, which is the correct binary digit for the current position, and carries `total // 2`, which is the correct amount to add to the next higher position.

If one string is shorter, the algorithm treats missing bits as `0`. This matches normal arithmetic.

The loop continues while either string has remaining bits or there is a carry. Therefore no input bit or final carry is lost.

Since the result bits are generated from right to left, reversing them produces the correct binary sum from most significant to least significant.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(max(m, n))` | We process each bit once |
| Space | `O(max(m, n))` | The result can be one bit longer than the longer input |

Here, `m = len(a)` and `n = len(b)`.

## Implementation

```python
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i = len(a) - 1
        j = len(b) - 1
        carry = 0
        ans = []

        while i >= 0 or j >= 0 or carry:
            total = carry

            if i >= 0:
                total += ord(a[i]) - ord("0")
                i -= 1

            if j >= 0:
                total += ord(b[j]) - ord("0")
                j -= 1

            ans.append(str(total % 2))
            carry = total // 2

        return "".join(reversed(ans))
```

## Code Explanation

Start from the rightmost bit of each string:

```python
i = len(a) - 1
j = len(b) - 1
```

Initialize the carry:

```python
carry = 0
```

Store answer bits in reverse order:

```python
ans = []
```

The loop continues while there are bits left or a carry remains:

```python
while i >= 0 or j >= 0 or carry:
```

Begin each column addition with the carry:

```python
total = carry
```

If `a` still has a bit, add it:

```python
if i >= 0:
    total += ord(a[i]) - ord("0")
    i -= 1
```

If `b` still has a bit, add it:

```python
if j >= 0:
    total += ord(b[j]) - ord("0")
    j -= 1
```

The current binary result bit is:

```python
total % 2
```

The carry for the next position is:

```python
total // 2
```

Finally, reverse and join:

```python
return "".join(reversed(ans))
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.addBinary("11", "1") == "100"
    assert s.addBinary("1010", "1011") == "10101"
    assert s.addBinary("0", "0") == "0"
    assert s.addBinary("1", "0") == "1"
    assert s.addBinary("1111", "1") == "10000"
    assert s.addBinary("101", "11") == "1000"
    assert s.addBinary("100", "110010") == "110110"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"11" + "1"` | Official example |
| `"1010" + "1011"` | Official example with longer result |
| `"0" + "0"` | Smallest values |
| `"1" + "0"` | No carry |
| `"1111" + "1"` | Carry through all bits |
| `"101" + "11"` | Different lengths |
| `"100" + "110010"` | Much different lengths |