# LeetCode 258: Add Digits

## Problem Restatement

We are given a non-negative integer `num`.

Repeatedly add all of its digits until the result has only one digit.

Return that final one-digit number.

Example:

```python
num = 38
```

First add its digits:

```python
3 + 8 = 11
```

The result still has two digits, so add again:

```python
1 + 1 = 2
```

Now the result has one digit.

Answer:

```python
2
```

The follow-up asks for an `O(1)` solution without loops or recursion. The input satisfies `0 <= num <= 2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A non-negative integer `num` |
| Output | The final one-digit digit sum |
| Process | Repeatedly sum digits |
| Follow-up | Solve in constant time |

Example function shape:

```python
def addDigits(num: int) -> int:
    ...
```

## Examples

Example 1:

```python
num = 38
```

Digit sum:

```python
3 + 8 = 11
```

Digit sum again:

```python
1 + 1 = 2
```

Answer:

```python
2
```

Example 2:

```python
num = 0
```

`0` already has one digit.

Answer:

```python
0
```

Example 3:

```python
num = 9
```

`9` already has one digit.

Answer:

```python
9
```

Example 4:

```python
num = 10
```

Digit sum:

```python
1 + 0 = 1
```

Answer:

```python
1
```

## First Thought: Simulate the Process

The problem statement directly describes a process.

While the number has at least two digits, replace it with the sum of its digits.

To get the digits, repeatedly take:

```python
num % 10
```

and remove the last digit with:

```python
num //= 10
```

A simulation solution is straightforward.

```python
class Solution:
    def addDigits(self, num: int) -> int:
        while num >= 10:
            total = 0

            while num > 0:
                total += num % 10
                num //= 10

            num = total

        return num
```

This solution is accepted and easy to reason about.

## Problem With Simulation

The follow-up asks for constant time.

The simulation repeatedly reads digits. For normal constraints this is still fast, but it does not satisfy the mathematical follow-up.

We need a direct formula for the final digit.

## Key Insight

This problem asks for the digital root of `num`.

In base 10, a number and its digit sum have the same remainder modulo `9`.

For example:

```python
38 % 9 = 2
```

and:

```python
(3 + 8) % 9 = 11 % 9 = 2
```

Adding digits preserves the remainder modulo `9`.

So the final one-digit answer must match the original number modulo `9`.

There is one special detail.

If the number is positive and divisible by `9`, the answer is `9`, not `0`.

Examples:

```python
9  -> 9
18 -> 9
27 -> 9
```

But for `0`, the answer is `0`.

## Formula

For `num > 0`, the result cycles like this:

| `num % 9` | Digital root |
|---|---|
| `1` | `1` |
| `2` | `2` |
| `3` | `3` |
| `4` | `4` |
| `5` | `5` |
| `6` | `6` |
| `7` | `7` |
| `8` | `8` |
| `0` | `9` |

A compact formula is:

```python
1 + (num - 1) % 9
```

This works for every positive integer.

For `num = 0`, return `0`.

## Algorithm

1. If `num == 0`, return `0`.
2. Otherwise return:

```python
1 + (num - 1) % 9
```

## Correctness

Adding the digits of a number preserves its remainder modulo `9`.

After repeating this operation, the final result is a single digit from `0` to `9`.

For every positive number, the final digit must be in `1` through `9`.

If `num % 9` is between `1` and `8`, the final digit is exactly that remainder.

If `num % 9 == 0` and `num > 0`, the final digit must be `9`, because `9` is the only positive one-digit number divisible by `9`.

The formula:

```python
1 + (num - 1) % 9
```

maps positive integers to exactly this cycle.

The separate `num == 0` case returns `0`, which is already a one-digit number.

Therefore the algorithm returns the correct repeated digit sum.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | Only arithmetic operations |
| Space | `O(1)` | No extra data structure |

## Implementation

```python
class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0

        return 1 + (num - 1) % 9
```

## Code Explanation

The first branch handles zero:

```python
if num == 0:
    return 0
```

Zero is already a single digit.

For every positive number, we use the digital root formula:

```python
return 1 + (num - 1) % 9
```

Subtracting `1` before taking modulo shifts the cycle so that multiples of `9` map to `9` instead of `0`.

## Testing

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

    assert s.addDigits(38) == 2
    assert s.addDigits(0) == 0
    assert s.addDigits(9) == 9
    assert s.addDigits(10) == 1
    assert s.addDigits(18) == 9
    assert s.addDigits(99) == 9
    assert s.addDigits(12345) == 6
    assert s.addDigits(2147483647) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `38` | Standard multi-step example |
| `0` | Special case |
| `9` | Positive multiple of nine |
| `10` | Simple digit sum |
| `18` | Multiple of nine with two digits |
| `99` | Larger multiple of nine |
| `12345` | Normal multi-digit number |
| `2147483647` | Upper-range style input |