Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Example 1:
Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.
Example 2:
Input: num = 0 Output: 0
Constraints:
0 <= num <= 231 - 1
Follow up: Could you do it without any loop/recursion in O(1) runtime?
Problem Overview: Given a non‑negative integer num, repeatedly add its digits until the result becomes a single digit. For example, 38 → 3 + 8 = 11 → 1 + 1 = 2. The task is to compute this final single-digit result.
Approach 1: Iterative Digit Sum (Simulation) (Time: O(d * k), Space: O(1))
This approach directly simulates the process described in the problem. Extract digits using modulo (% 10) and division (/ 10), sum them, and repeat the process while the number has more than one digit. Each pass processes all digits once, so the cost depends on the number of digits d and how many iterations k are needed until a single digit remains. This method uses constant extra space and works in every language without relying on mathematical shortcuts. It’s a good baseline solution and demonstrates basic number manipulation techniques from simulation.
Approach 2: Digital Root Formula (Mathematical) (Time: O(1), Space: O(1))
The repeated digit sum has a well-known pattern in number theory. The result is called the digital root. For any positive integer, the digital root can be computed using the formula 1 + (num - 1) % 9. If num is 0, the result is 0. This works because numbers that differ by multiples of 9 share the same digital root. Instead of iterating through digits multiple times, the modulo operation jumps directly to the final answer. This turns the problem into a constant-time computation and avoids loops entirely.
Recommended for interviews: Start with the iterative simulation. It proves you understand digit extraction and the process defined in the problem. Then mention the digital root observation from math. Interviewers usually expect the O(1) formula as the optimal solution because it shows deeper insight into number properties rather than just implementing the steps literally.
The iterative approach involves summing the digits of the number repeatedly until the sum becomes a single-digit number. This is a straightforward approach and uses basic loops to repeatedly process the digits of the number.
The function addDigits takes an integer which it divides into its individual digits by taking the modulo and integer division operations. It sums these digits and repeats the process until the result is a single digit.
The mathematical approach leverages a known number theory result related to digit root which can be deduced using modulo 9 arithmetic. The result for the repeated digit sum is equivalent to the number modulo 9, except that when the number is zero it should remain zero.
This C solution uses modulo 9 to calculate the digit root. This gives us a constant time solution which is highly efficient.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) where n is the number of digits in the number. This is because each iteration sums the digits. Space Complexity: O(1) because we only use a constant amount of extra space. |
| Mathematical Approach | Time Complexity: O(1). Space Complexity: O(1). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Digit Sum (Simulation) | O(d * k) | O(1) | When implementing the process directly or when mathematical shortcuts are not known |
| Digital Root Mathematical Formula | O(1) | O(1) | Best choice for interviews and production due to constant-time computation |
Add Digits | LeetCode problem 258 • Technosage • 11,184 views views
Watch 9 more video solutions →Practice Add Digits with our built-in code editor and test cases.
Practice on FleetCode