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 efficiently.
Approach 1: Iterative Digit Summation (Simulation) (Time: O(log n), Space: O(1))
This approach directly simulates the process described in the problem. Extract digits using modulo (num % 10) and integer division (num / 10), sum them, and repeat the process until the number becomes a single digit. Each pass processes all digits of the current number, which takes O(d) where d is the digit count (≈ log10(n)). Because the result quickly shrinks to a smaller number, the overall runtime stays around O(log n) with constant extra space. This method is straightforward and a good baseline when working with simulation problems.
Approach 2: Digital Root Formula (Mathematical Approach) (Time: O(1), Space: O(1))
The repeated digit-sum process forms a well-known pattern called the digital root. In base 10, the final value depends on the remainder when dividing by 9. The formula is: 0 if num == 0, otherwise 1 + (num - 1) % 9. This works because digit sums preserve the number’s value modulo 9. Instead of looping through digits, a single arithmetic operation returns the result instantly. This technique comes from number theory and is common in math-based interview questions where a pattern replaces brute computation.
Recommended for interviews: Start with the iterative approach since it matches the problem statement and demonstrates clear reasoning. After that, mention the digital root observation and derive the O(1) formula. Interviewers typically expect candidates to recognize the mathematical pattern, since it reduces repeated digit processing to constant time.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
| 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). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Digit Summation (Simulation) | O(log n) | O(1) | When implementing the process exactly as described or when mathematical patterns are not obvious. |
| Digital Root Mathematical Formula | O(1) | O(1) | Best choice for interviews and production when constant-time arithmetic is preferred. |
Add Two Numbers - Leetcode 2 - Python • NeetCode • 293,331 views views
Watch 9 more video solutions →Practice Add Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor