# LeetCode 66: Plus One

## Problem Restatement

We are given a large integer represented as an array of digits.

The digits are ordered from most significant to least significant. This means the leftmost digit is the largest place value.

We need to add one to the integer and return the resulting digits as an array.

The input has no leading zeroes, and each element is a single digit from `0` to `9`. The official constraints are `1 <= digits.length <= 100` and `0 <= digits[i] <= 9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of digits |
| Output | A list of digits after adding one |
| Digit order | Most significant to least significant |
| Leading zeroes | The input does not contain leading zeroes |

Function shape:

```python
def plusOne(digits: list[int]) -> list[int]:
    ...
```

## Examples

For:

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

The array represents:

```text
123
```

After adding one:

```text
123 + 1 = 124
```

So the answer is:

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

For:

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

The number is `4321`.

After adding one, it becomes `4322`.

So the answer is:

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

For:

```python
digits = [9]
```

The number is `9`.

After adding one:

```text
9 + 1 = 10
```

So the answer is:

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

## First Thought: Convert to Integer

One simple idea is:

1. Convert the digit array into an integer.
2. Add one.
3. Convert the integer back into an array.

For example:

```python
digits = [1, 2, 3]
number = 123
number += 1
answer = [1, 2, 4]
```

This works in Python because Python integers can grow very large.

But the point of the problem is to handle the number as digits. In many languages, the integer could be too large for built-in numeric types.

So we should simulate addition directly on the array.

## Key Insight

When adding one manually, we start from the rightmost digit.

If the digit is less than `9`, we can simply add one and return.

For example:

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

But if the digit is `9`, adding one turns it into `0` and creates a carry.

For example:

```python
[1, 2, 9] -> [1, 3, 0]
```

The carry continues left while we keep seeing `9`.

The only time the array grows is when every digit is `9`.

For example:

```python
[9, 9, 9] -> [1, 0, 0, 0]
```

## Algorithm

Scan the array from right to left.

For each index `i`:

1. If `digits[i] < 9`, increment it and return the array.
2. Otherwise, set `digits[i] = 0` and continue left.

If the loop finishes, then every digit was `9`.

Return a new array:

```python
[1] + digits
```

At that point, `digits` contains only zeroes.

## Correctness

The algorithm processes digits from least significant to most significant, which is exactly how addition with carry works.

If a digit is less than `9`, adding one to it creates no carry. All digits to its left remain unchanged, and all digits to its right have already been handled. Returning immediately gives the correct result.

If a digit is `9`, adding one changes it to `0` and carries one to the next digit on the left. Setting it to `0` and continuing preserves the correct addition behavior.

If every digit is `9`, then each digit becomes `0` and a carry remains after the most significant digit. The only valid result is a leading `1` followed by all zeroes, which the algorithm returns.

Therefore the algorithm returns exactly the original integer plus one.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | In the worst case, we scan every digit |
| Space | `O(1)` | We modify the input array in place, except when a new leading digit is needed |

The returned array may have length `n + 1` when the input is all `9`s.

## Implementation

```python
class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits

            digits[i] = 0

        return [1] + digits
```

## Code Explanation

We start from the last digit:

```python
for i in range(len(digits) - 1, -1, -1):
```

If the digit is smaller than `9`, no carry continues:

```python
if digits[i] < 9:
    digits[i] += 1
    return digits
```

If the digit is `9`, it becomes `0`:

```python
digits[i] = 0
```

Then the loop continues to the digit on the left.

If the loop finishes, all digits were `9`, so we need a new leading `1`:

```python
return [1] + digits
```

## Testing

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

    assert s.plusOne([1, 2, 3]) == [1, 2, 4]
    assert s.plusOne([4, 3, 2, 1]) == [4, 3, 2, 2]
    assert s.plusOne([9]) == [1, 0]
    assert s.plusOne([1, 2, 9]) == [1, 3, 0]
    assert s.plusOne([9, 9, 9]) == [1, 0, 0, 0]
    assert s.plusOne([0]) == [1]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3]` | No carry |
| `[4,3,2,1]` | No carry with longer input |
| `[9]` | Single digit creates new leading digit |
| `[1,2,9]` | One carry |
| `[9,9,9]` | Carry through all digits |
| `[0]` | Smallest numeric value |