# LeetCode 415: Add Strings

## Problem Restatement

We are given two non-negative integers as strings:

```python
num1
num2
```

Return their sum as a string.

We cannot use a built-in big integer library.

We also cannot directly convert the whole input strings into integers.

So this is manual addition, the same way we add numbers on paper.

The source problem states that `num1` and `num2` contain only digits, have no leading zeroes except `"0"` itself, and each length is between `1` and `10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two non-negative integer strings `num1` and `num2` |
| Output | Their sum as a string |
| Digits | Both strings contain only digits |
| Restriction | Do not directly convert the whole strings to integers |
| Leading zeroes | Inputs have no leading zeroes except `"0"` |

Example function shape:

```python
def addStrings(num1: str, num2: str) -> str:
    ...
```

## Examples

Example 1:

```python
num1 = "11"
num2 = "123"
```

The answer is:

```python
"134"
```

Manual addition:

```text
  123
+  11
-----
  134
```

Example 2:

```python
num1 = "456"
num2 = "77"
```

The answer is:

```python
"533"
```

Manual addition:

```text
  456
+  77
-----
  533
```

Example 3:

```python
num1 = "0"
num2 = "0"
```

The answer is:

```python
"0"
```

## First Thought: Convert to Integer

The easiest code would be:

```python
return str(int(num1) + int(num2))
```

But this violates the rule.

The problem is designed to handle very large numbers stored as strings. We must add digits ourselves.

## Key Insight

Addition works from right to left.

At each position, we add:

```python
digit_from_num1 + digit_from_num2 + carry
```

Then:

```python
result_digit = total % 10
carry = total // 10
```

For example:

```python
9 + 7 + 0 = 16
```

The current result digit is:

```python
6
```

and the carry is:

```python
1
```

We repeat this until both strings are fully processed and there is no carry left.

## Algorithm

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Current index in `num1`, starting from the end |
| `j` | Current index in `num2`, starting from the end |

Initialize:

```python
i = len(num1) - 1
j = len(num2) - 1
carry = 0
result = []
```

Then repeat while either string has digits left or `carry` remains:

1. Read the current digit from `num1`, or use `0` if `i` is out of bounds.
2. Read the current digit from `num2`, or use `0` if `j` is out of bounds.
3. Add both digits and `carry`.
4. Append the ones digit to `result`.
5. Update `carry`.
6. Move both pointers left.

At the end, reverse `result` and join it into a string.

## Correctness

The algorithm simulates standard decimal addition column by column from right to left.

At each step, it computes the exact sum of the two digits at the current decimal place plus the carry from the previous lower place.

The expression:

```python
total % 10
```

gives the digit that belongs in the current place.

The expression:

```python
total // 10
```

gives the carry that must be added to the next higher place.

If one string is shorter, the algorithm treats its missing digits as `0`, which is exactly how manual addition aligns numbers by their rightmost digits.

The loop continues while there are unprocessed digits or a remaining carry, so no digit or final carry is lost.

Because the result digits are produced from least significant to most significant, reversing them gives the correct final order.

Therefore, the returned string is the exact sum of `num1` and `num2`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(max(m, n))` | We process each digit once |
| Space | `O(max(m, n))` | The result may contain one more digit than the longer input |

Here:

| Symbol | Meaning |
|---|---|
| `m` | Length of `num1` |
| `n` | Length of `num2` |

Ignoring the returned output string, the extra working space is `O(1)` besides the result buffer.

## Implementation

```python
from typing import List

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            digit1 = ord(num1[i]) - ord("0") if i >= 0 else 0
            digit2 = ord(num2[j]) - ord("0") if j >= 0 else 0

            total = digit1 + digit2 + carry

            result.append(str(total % 10))
            carry = total // 10

            i -= 1
            j -= 1

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

## Code Explanation

We start from the last digit of each string:

```python
i = len(num1) - 1
j = len(num2) - 1
```

The carry starts at zero:

```python
carry = 0
```

The result list stores digits in reverse order:

```python
result = []
```

The loop continues as long as there is something left to add:

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

We convert one digit character into its numeric value:

```python
ord(num1[i]) - ord("0")
```

This avoids converting the whole string into an integer.

If the pointer is already out of bounds, we use `0`:

```python
digit1 = ord(num1[i]) - ord("0") if i >= 0 else 0
```

Then we add the two digits and the carry:

```python
total = digit1 + digit2 + carry
```

The current output digit is:

```python
total % 10
```

The carry for the next column is:

```python
total // 10
```

After processing this column, both pointers move left:

```python
i -= 1
j -= 1
```

Finally, we reverse the collected digits:

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

## Testing

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

    assert s.addStrings("11", "123") == "134"
    assert s.addStrings("456", "77") == "533"
    assert s.addStrings("0", "0") == "0"
    assert s.addStrings("9", "1") == "10"
    assert s.addStrings("999", "1") == "1000"
    assert s.addStrings("1", "9999") == "10000"
    assert s.addStrings("123456789", "987654321") == "1111111110"

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| `"11" + "123"` | Standard example with different lengths |
| `"456" + "77"` | Carry inside the number |
| `"0" + "0"` | Zero case |
| `"9" + "1"` | Final carry creates a new digit |
| `"999" + "1"` | Carry propagates through many digits |
| `"1" + "9999"` | Very different lengths |
| Large values | Confirms digit-by-digit addition works |