Add digits till the result has one digit

Problem Link : Add Digits Till Result Has One Digit

Problem Statement

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Examples

Example 1:

Input: num = 38
Process:
38 → 3 + 8 = 11
11 → 1 + 1 = 2
Output: 2

Example 2:

Input: num = 0
Output: 0

Constraints

0 <= num <= 2^31 - 1

Intuition

The naive approach would involve repeatedly summing the digits using a loop or recursion until a single-digit result is obtained.

However, this can be optimized using a mathematical insight called the digital root, which is based on modulo arithmetic in base 10:

The digital root of a number is the value obtained by repeatedly summing the digits of the number until a single-digit number is obtained.

For base 10 numbers, the formula for the digital root is:

If num == 0 → return 0  
If num % 9 == 0 → return 9  
Else → return num % 9

This is known as the digital root formula.

Approach

We use a constant time approach (O(1)) based on the modulo 9 property:

If the number is 0, return 0.
If the number is divisible by 9, return 9.
Otherwise, return num % 9.

Java Code

class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0;
        if (num % 9 == 0) return 9;
        return num % 9;
    }
}

Alternatively, the formula can be compressed into one line:

class Solution {
    public int addDigits(int num) {
        return (num == 0) ? 0 : (num % 9 == 0 ? 9 : num % 9);
    }
}

Dry Run

Input: `num = 38`

num % 9 = 38 % 9 = 2
Since 38 is not divisible by 9, return 2

Input: `num = 18`

num % 9 = 0, so return 9

Input: `num = 0`

Return 0 directly

Time Complexity

O(1) — Constant time computation using a mathematical formula

Space Complexity

O(1) — No extra space used

Conclusion

This problem, although appearing iterative, can be solved in constant time using the digital root technique. The modulo-based solution is efficient, elegant, and well-suited for large input values.