LeetCode 258 - Add Digits

The problem asks us to repeatedly transform a number by summing its digits until only a single digit remains. The final single digit should then be returned. For example, if the input is 38, we first compute 3 + 8 = 11.

leetcodeeasymathsimulationnumber-theory

LeetCode Problem 258

Difficulty: 🟢 Easy
Topics: Math, Simulation, Number Theory

Solution

Problem Understanding

The problem asks us to repeatedly transform a number by summing its digits until only a single digit remains. The final single digit should then be returned.

For example, if the input is 38, we first compute 3 + 8 = 11. Since 11 still has more than one digit, we repeat the process and compute 1 + 1 = 2. The result 2 is a single digit, so that becomes the answer.

The input is a non-negative integer num. The output is also an integer, specifically the final one-digit value obtained after repeatedly summing digits.

The constraint 0 <= num <= 2^31 - 1 tells us the input can be as large as a 32-bit signed integer. Even though this is not extremely large, the follow-up question strongly hints that there is a mathematical property that allows us to avoid simulation entirely and compute the result in constant time.

There are several important edge cases to consider:

  • If num = 0, the answer must remain 0. This is special because the mathematical shortcut behaves slightly differently for zero.
  • If num is already a single digit, the answer should simply be the number itself.
  • Large values such as 2147483647 must still work correctly without overflow or excessive computation.
  • Numbers whose digit sum repeatedly collapses multiple times, such as 99999, should eventually converge correctly to a single digit.

Approaches

Brute Force Simulation

The most direct solution is to repeatedly compute the sum of the digits until the number becomes a single digit.

To compute the digit sum, we can repeatedly extract digits using modulo and integer division:

  • digit = num % 10
  • num //= 10

We keep adding the extracted digits into a running total. Once all digits are processed, we replace the original number with the digit sum and repeat the process until the number is less than 10.

This approach is correct because it exactly follows the process described in the problem statement. Every iteration reduces the number toward a smaller value, eventually producing a single digit.

Although this solution is efficient enough for the given constraints, it still involves loops and repeated digit extraction. The follow-up specifically asks whether we can avoid loops and recursion entirely.

Optimal Mathematical Insight

The key observation is that repeatedly summing digits produces the number's digital root.

The digital root has a well-known mathematical property based on modulo 9:

  • If a number is divisible by 9, its digital root is 9
  • Otherwise, the digital root is num % 9
  • The only exception is 0, whose digital root is 0

This works because a number and the sum of its digits have the same remainder modulo 9.

For example:

  • 38 % 9 = 2
  • 3 + 8 = 11
  • 1 + 1 = 2

Both produce the same final result.

Using this property, we can compute the answer in constant time with no loops or recursion.

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(1) Repeatedly sums digits until one digit remains
Optimal O(1) O(1) Uses digital root mathematical property

Algorithm Walkthrough

Optimal Algorithm

  1. Check whether the input number is 0.

This is necessary because the digital root formula behaves differently for zero. If we directly applied the modulo rule, we would incorrectly return 9 for 0. 2. Compute num % 9.

The remainder modulo 9 captures the same repeated digit-sum behavior as the simulation process. 3. If the remainder is 0, return 9.

Any positive multiple of 9 eventually reduces to 9. Examples include:

  • 9 -> 9
  • 18 -> 1 + 8 = 9
  • 99 -> 9 + 9 = 18 -> 1 + 8 = 9
  1. Otherwise, return the remainder.

For all non-multiples of 9, the remainder itself is the final single-digit answer.

Why it works

The correctness comes from the modulo 9 property of decimal numbers. Every power of 10 is congruent to 1 modulo 9, which means a number and the sum of its digits always share the same remainder modulo 9.

For example:

$$38 = 3 \times 10 + 8$$

Since:

$$10 \equiv 1 \pmod{9}$$

We get:

$$38 \equiv 3 + 8 \pmod{9}$$

Repeating this process preserves the same modulo value until only one digit remains. That final digit is the digital root.

The central mathematical relationship is:

$\operatorname{digital_root}(n)=\begin{cases}0 & n=0 \ 9 & n\bmod 9=0 \text{ and } n>0 \ n\bmod 9 & \text{otherwise}\end{cases}$

Python Solution

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        
        remainder = num % 9
        
        if remainder == 0:
            return 9
        
        return remainder

The implementation first handles the special case where the input is 0.

Next, it computes the remainder when dividing by 9. This remainder determines the digital root.

If the remainder is 0, the number must be a positive multiple of 9, so the answer is 9.

Otherwise, the remainder itself is returned.

This implementation directly follows the mathematical derivation and avoids any loops or recursion.

Go Solution

func addDigits(num int) int {
    if num == 0 {
        return 0
    }

    remainder := num % 9

    if remainder == 0 {
        return 9
    }

    return remainder
}

The Go implementation is almost identical to the Python version. Since the input constraint fits comfortably within Go's int type on LeetCode, no special overflow handling is required.

Go uses explicit variable declarations with :=, while Python relies on dynamic typing. Otherwise, the logic and edge case handling remain the same.

Worked Examples

Example 1

Input:

num = 38

Simulation process:

Step Current Number Digit Sum
1 38 3 + 8 = 11
2 11 1 + 1 = 2

Final answer:

2

Mathematical approach:

Value Result
38 % 9 2
Final Answer 2

Example 2

Input:

num = 0

Since the number is already 0, we immediately return 0.

Check Result
num == 0 true
Final Answer 0

Additional Example

Input:

num = 99

Simulation:

Step Current Number Digit Sum
1 99 9 + 9 = 18
2 18 1 + 8 = 9

Mathematical approach:

Value Result
99 % 9 0
Positive multiple of 9 yes
Final Answer 9

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a few arithmetic operations are performed
Space O(1) No additional memory proportional to input size is used

The optimal solution performs a constant number of operations regardless of the input size. Unlike the brute-force simulation, there is no repeated digit extraction or iteration.

Test Cases

solution = Solution()

assert solution.addDigits(38) == 2        # Example case
assert solution.addDigits(0) == 0         # Zero edge case
assert solution.addDigits(5) == 5         # Single digit remains unchanged
assert solution.addDigits(9) == 9         # Single digit multiple of 9
assert solution.addDigits(18) == 9        # Multiple of 9
assert solution.addDigits(99) == 9        # Repeated reduction to 9
assert solution.addDigits(10) == 1        # Simple two-digit case
assert solution.addDigits(123) == 6       # Multiple digit reductions
assert solution.addDigits(99999) == 9     # Large repeated sums
assert solution.addDigits(2147483647) == 1  # Maximum 32-bit integer
Test Why
38 Verifies the main example
0 Confirms special-case handling
5 Ensures single digits return unchanged
9 Tests single-digit multiple of 9
18 Verifies modulo-9 behavior
99 Tests repeated reductions
10 Validates simple carry behavior
123 Confirms standard digit summation
99999 Stress test for repeated reductions
2147483647 Confirms handling of maximum constraint value

Edge Cases

Input Equal to Zero

The value 0 is the most important special case in this problem. If we blindly applied the modulo formula, we might incorrectly return 9 because 0 % 9 == 0.

The implementation explicitly checks:

if num == 0:
    return 0

This guarantees correct behavior for zero.

Input Already a Single Digit

If the input is already between 1 and 9, the answer should simply be the number itself. For example:

  • 5 -> 5
  • 8 -> 8

The modulo formula naturally handles these cases because:

  • 5 % 9 = 5
  • 8 % 9 = 8

No additional logic is needed.

Positive Multiples of Nine

Numbers like 9, 18, 99, and 9999 are tricky because their modulo 9 result is 0, but their digital root should be 9, not 0.

For example:

18 -> 1 + 8 = 9

The implementation correctly handles this with:

if remainder == 0:
    return 9

This ensures all positive multiples of 9 produce the correct result.