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:

num = 38

First add its digits:

3 + 8 = 11

The result still has two digits, so add again:

1 + 1 = 2

Now the result has one digit.

Answer:

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

Example function shape:

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

Examples

Example 1:

num = 38

Digit sum:

3 + 8 = 11

Digit sum again:

1 + 1 = 2

Answer:

2

Example 2:

num = 0

0 already has one digit.

Answer:

0

Example 3:

num = 9

9 already has one digit.

Answer:

9

Example 4:

num = 10

Digit sum:

1 + 0 = 1

Answer:

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:

num % 10

and remove the last digit with:

num //= 10

A simulation solution is straightforward.

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:

38 % 9 = 2

and:

(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:

9  -> 9
18 -> 9
27 -> 9

But for 0, the answer is 0.

Formula

For num > 0, the result cycles like this:

A compact formula is:

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:

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:

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

Implementation

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:

if num == 0:
    return 0

Zero is already a single digit.

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

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

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: