# LeetCode 989: Add to Array-Form of Integer

## Problem Restatement

We are given an integer `num` in array form.

That means each element of `num` is one digit, ordered from most significant to least significant.

For example:

```python
num = [1, 3, 2, 1]
```

represents:

```python
1321
```

We are also given an integer `k`.

We need to return the array-form of:

```python
num + k
```

The official constraints include `1 <= num.length <= 10^4`, each digit is between `0` and `9`, `num` has no leading zeros except zero itself, and `1 <= k <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array-form integer `num` and integer `k` |
| Output | Array-form representation of `num + k` |
| Digit order | Most significant digit first |
| Main rule | Add without relying on converting the whole array to one integer |

Function shape:

```python
def addToArrayForm(num: list[int], k: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
num = [1, 2, 0, 0]
k = 34
```

The array represents `1200`.

Then:

```python
1200 + 34 = 1234
```

Answer:

```python
[1, 2, 3, 4]
```

Example 2:

```python
num = [2, 7, 4]
k = 181
```

The array represents `274`.

Then:

```python
274 + 181 = 455
```

Answer:

```python
[4, 5, 5]
```

Example 3:

```python
num = [2, 1, 5]
k = 806
```

The array represents `215`.

Then:

```python
215 + 806 = 1021
```

Answer:

```python
[1, 0, 2, 1]
```

## First Thought: Convert to Integer

A simple solution is to convert the digit array into an integer, add `k`, then convert the result back to an array.

```python
class Solution:
    def addToArrayForm(self, num: list[int], k: int) -> list[int]:
        value = 0

        for digit in num:
            value = value * 10 + digit

        value += k

        return [int(ch) for ch in str(value)]
```

This is easy to understand.

## Problem With Full Conversion

The array can contain up to `10^4` digits.

In many languages, this number is far larger than the built-in integer range.

Python supports large integers, but LeetCode problems should usually be solved in a language-independent way when the input is clearly digit-based.

We should simulate addition the same way we do it by hand.

## Key Insight

Addition starts from the least significant digit.

In the array, that is the rightmost digit.

Instead of converting all of `num` into an integer, we add `k` into the array from right to left.

At each step:

```python
total = current_digit + k
```

The new digit is:

```python
total % 10
```

The remaining carry is:

```python
total // 10
```

We can reuse `k` as the carry because after processing one digit, the rest of `k` still needs to be added to the next higher place.

## Algorithm

Start from the last index of `num`.

Maintain an answer list in reverse order.

While there are digits left in `num` or `k > 0`:

1. If there is a current digit, add it to `k`.
2. The next result digit is `k % 10`.
3. Append that digit to `answer`.
4. Update `k = k // 10`.
5. Move one digit left in `num`.

Finally, reverse `answer`.

## Correctness

The algorithm processes digits from right to left, starting with the ones place.

At each step, `k` contains the remaining value that must be added to the current decimal position and all higher positions. When the current digit is added to `k`, the ones digit of that sum is exactly the result digit for the current position.

The algorithm appends `k % 10`, which is that correct digit, then replaces `k` with `k // 10`, which is the carry and remaining higher-place value.

This matches ordinary decimal addition.

The loop continues until both the original digits are exhausted and no carry remains. Therefore, every digit of the sum is produced exactly once.

Since digits are produced from least significant to most significant, reversing the answer gives the required array-form order.

## Complexity

Let `n = len(num)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + log k)` | We process all digits of `num` and any remaining digits of `k` |
| Space | `O(n + log k)` | The answer array stores the result |

## Implementation

```python
class Solution:
    def addToArrayForm(self, num: list[int], k: int) -> list[int]:
        answer = []
        i = len(num) - 1

        while i >= 0 or k > 0:
            if i >= 0:
                k += num[i]

            answer.append(k % 10)
            k //= 10
            i -= 1

        answer.reverse()
        return answer
```

## Code Explanation

We build the answer from right to left:

```python
answer = []
i = len(num) - 1
```

The loop continues while there is still a digit in `num` or a remaining carry in `k`:

```python
while i >= 0 or k > 0:
```

If a digit exists at position `i`, add it into `k`:

```python
if i >= 0:
    k += num[i]
```

The current result digit is the last decimal digit of `k`:

```python
answer.append(k % 10)
```

Then remove that digit and keep the remaining carry:

```python
k //= 10
```

Move left in the original array:

```python
i -= 1
```

Because digits were appended in reverse order, reverse before returning:

```python
answer.reverse()
return answer
```

## Testing

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

    assert s.addToArrayForm([1, 2, 0, 0], 34) == [1, 2, 3, 4]
    assert s.addToArrayForm([2, 7, 4], 181) == [4, 5, 5]
    assert s.addToArrayForm([2, 1, 5], 806) == [1, 0, 2, 1]
    assert s.addToArrayForm([9, 9, 9], 1) == [1, 0, 0, 0]
    assert s.addToArrayForm([0], 10000) == [1, 0, 0, 0, 0]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[1,2,0,0]`, `34` | `[1,2,3,4]` | Basic sample |
| `[2,7,4]`, `181` | `[4,5,5]` | Carry across digits |
| `[2,1,5]`, `806` | `[1,0,2,1]` | Result gains one digit |
| `[9,9,9]`, `1` | `[1,0,0,0]` | Full carry propagation |
| `[0]`, `10000` | `[1,0,0,0,0]` | Remaining `k` digits after array ends |