Add Digits: The Digital Root Formula

LeetCode Add Digits (Problem 258) asks you to take a non-negative integer and repeatedly add its digits until the result is a single digit. For example, given 38, you compute 3 + 8 = 11, then 1 + 1 = 2, and return 2.

The simulation approach is simple enough, but there is an O(1) math formula that solves it in constant time. That formula has a name: the digital root.

Problem description

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. Return that single digit.

• Input: num = 38
• Output: 2
• Explanation: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

The approach

There are two ways to solve this problem.

Simulation (loop until single digit)

The direct approach is exactly what the problem describes. While the number has more than one digit, extract each digit, sum them, and replace the number with that sum. You keep going until only one digit remains.

Extracting digits uses the familiar num % 10 and num //= 10 pattern. You have seen this same micro-pattern in Palindrome Number and Happy Number.

Digital root formula (O(1))

There is a well-known mathematical shortcut called the digital root. It turns out that repeatedly summing digits is equivalent to computing the number modulo 9, with one adjustment for multiples of 9.

The formula is:

• If num == 0, return 0
• Otherwise, return 1 + (num - 1) % 9

Why does this work? When you write a number in decimal, each digit contributes its value times a power of 10. Since 10 ≡ 1 (mod 9), every power of 10 is also congruent to 1 modulo 9. That means the number itself is congruent to the sum of its digits modulo 9. Repeating the process does not change the remainder. The 1 + (num - 1) % 9 formulation handles the edge case where the digital root should be 9 (not 0) for nonzero multiples of 9.

The solution

Simulation approach

def add_digits_loop(num):
    while num >= 10:
        total = 0
        while num > 0:
            total += num % 10
            num //= 10
        num = total
    return num

The outer loop runs until num is a single digit. The inner loop extracts each digit with num % 10 and removes it with num //= 10. After summing all the digits, you assign the total back to num and check again.

O(1) digital root formula

def add_digits(num):
    if num == 0:
        return 0
    return 1 + (num - 1) % 9

No loops, no digit extraction. Just one line of arithmetic. This is the approach interviewers often hope you will discover after presenting the simulation first.

Step-by-step walkthrough

Let's trace through both approaches with num = 38.

Both approaches produce the same answer. The simulation takes two iterations. The formula takes constant time.

Complexity analysis

The simulation processes each digit in each round, and the number of digits is proportional to log base 10 of n. The number of rounds is also bounded by the number of digits. The digital root formula skips all of that with a single modulo operation.

Building blocks

This problem decomposes into reusable pieces you will recognize from other problems.

1. Digit extraction with mod and div

Pulling digits off a number one at a time using num % 10 and num //= 10. This is the same micro-pattern used in Happy Number, Palindrome Number, and Reverse Integer.

while num > 0:
    digit = num % 10
    num //= 10

2. Modular arithmetic insight

Recognizing that a property of a number (like its digit sum) is invariant under modular arithmetic. The digital root formula relies on the fact that 10 ≡ 1 (mod 9). This kind of modular reasoning appears in problems involving remainders, cyclic patterns, and number theory.

On CodeBricks, you drill each building block separately. When they appear combined in a new problem, you recognize both pieces instantly.

Edge cases

• num = 0: The digital root of 0 is 0. The simulation loop never executes since 0 is already a single digit. The formula handles this with the explicit check.
• Single-digit numbers (1 through 9): Already a single digit, so return the number itself. The formula gives 1 + (n - 1) % 9, which equals n for values 1 through 9.
• num = 9 (and multiples of 9): The digital root is 9, not 0. The formula 1 + (num - 1) % 9 correctly produces 9 because (9 - 1) % 9 = 8, and 1 + 8 = 9. A naive num % 9 would incorrectly return 0.
• Large numbers: The formula handles any input in O(1). The simulation also converges quickly because the digit sum of even a very large number drops to at most a few digits after one round.

From understanding to recall

You can read through this solution in a few minutes and follow every step. But understanding is not the same as being able to reproduce it under interview pressure two weeks from now.

That is where spaced repetition comes in. CodeBricks breaks Add Digits into its building blocks (digit extraction with mod/div, the digital root formula) and drills them at increasing intervals. You type each piece from scratch, building genuine recall rather than fragile familiarity. After a few review cycles, reaching for 1 + (num - 1) % 9 becomes automatic.

Related posts

• Happy Number - Another digit-processing problem that uses the same mod/div extraction loop, combined with cycle detection
• Palindrome Number - Digit manipulation without string conversion, using the same mod and div building block
• Power of Two - A different O(1) math trick for checking a number property, showing how a single formula can replace a loop