Given a non-negative integer num, you must repeatedly add all its digits until only one digit remains.
This is known as the digital root of a number.
Example:
Input: 38
3 + 8 = 11
1 + 1 = 2
Output = 2
Understanding the Problem
You repeatedly sum the digits of a number:
If the number has more than one digit, add its digits again.
Continue until only one digit remains.
This must repeat potentially many times, but the integer can be large.
Examples:
Input: 0 → Output: 0
Input: 99 → 9 + 9 = 18 → 1 + 8 = 9
We need to compute this efficiently.
Approach (Explained in Simple Language)
You can solve this problem in two ways:
Approach 1: Repeated digit summation using loops
Approach 2: Use the mathematical digital root formula (O(1) time)
We will explain both.
Approach 1: Repeated Summation (Simple Logic)
1. While the number has more than one digit
sum the digits
replace num with the sum
2. When num < 10
return num
This works but takes longer for very large numbers.
Approach 2: Digital Root Formula (Best Approach)
For any positive integer:
digital root = 1 + (num − 1) % 9
This works because of a well-known property of numbers in base 10.
Exceptions:
If num == 0 → output 0
Otherwise → use the formula
This gives constant-time O(1) performance.
Java Code (Repeated Summation)
public class AddDigits {
public int addDigits(int num) {
while (num >= 10) {
int sum = 0;
int temp = num;
while (temp > 0) {
sum += temp % 10;
temp /= 10;
}
num = sum;
}
return num;
}
public static void main(String[] args) {
AddDigits solution = new AddDigits();
System.out.println(solution.addDigits(38));
}
}
Java Code (Digital Root Formula)
public class AddDigitsFormula {
public int addDigits(int num) {
if (num == 0) {
return 0;
}
return 1 + (num - 1) % 9;
}
public static void main(String[] args) {
AddDigitsFormula solution = new AddDigitsFormula();
System.out.println(solution.addDigits(38));
}
}
Dry Run (Using Repeated Summation)
Input: num = 38
Initial: num = 38
num >= 10 → continue
First iteration
temp = 38
sum = 0
sum += 8 → sum = 8
temp = 3
sum += 3 → sum = 11
temp = 0
num = 11
Second iteration
temp = 11
sum = 0
sum += 1 → sum = 1
temp = 1
sum += 1 → sum = 2
temp = 0
num = 2
Now num < 10 → stop.
Output = 2
Dry Run (Using Formula)
Input: 38
digital root = 1 + (38 − 1) % 9
digital root = 1 + (37 % 9)
37 % 9 = 1
Answer = 1 + 1 = 2
Why This Approach Works
The repeated-digit-sum approach works directly by definition, but the digital root formula provides:
O(1) time
No loops
No recursion
It leverages number theory and properties of modulo 9.
This is the most optimal solution.