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 - 1Follow up: Could you do it without any loop/recursion in O(1) runtime?
The problem #258 Add Digits asks you to repeatedly add the digits of a non‑negative integer until the result becomes a single digit. A straightforward way to think about this is through simulation. Extract each digit using division or modulo operations, sum them, and repeat the process until the number has only one digit left. This approach closely mirrors how humans perform the operation.
A more optimized perspective comes from number theory. The repeated digit sum of a number follows a mathematical pattern known as the digital root. Instead of repeatedly iterating through digits, you can derive the final single-digit result directly using properties of numbers in base 10. This avoids loops and significantly improves efficiency.
The simulation approach is intuitive and easy to implement, while the mathematical observation allows for a constant-time computation. Understanding both methods is valuable in interviews because it demonstrates problem-solving intuition and mathematical optimization skills.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Digit Sum Simulation | O(log n) | O(1) |
| Digital Root Math Formula | O(1) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
A naive implementation of the above process is trivial. Could you come up with other methods?
What are all the possible results?
How do they occur, periodically or randomly?
You may find this <a href="https://en.wikipedia.org/wiki/Digital_root" target="_blank">Wikipedia article</a> useful.
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.
1def add_digits(num):
2 while num >= 10:
3 sum = 0
4 while num > 0:
5 sum += num % 10
6 num //= 10
7 num = sum
8 return num
9
10print(add_digits(38))Python's implementation uses loops to compute the sum of the digits repeatedly until a single-digit number is obtained.
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.
1using System;
2
public class AddDigitsMath {
public static int AddDigits(int num) {
if (num == 0) return 0;
return (num % 9 == 0) ? 9 : num % 9;
}
public static void Main() {
int num = 38;
Console.WriteLine(AddDigits(num));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of digit manipulation problems like Add Digits can appear in technical interviews, including FAANG-style interviews. They are often used to test basic problem-solving skills, mathematical insight, and the ability to optimize a brute-force solution.
No special data structure is required for this problem. The task mainly involves arithmetic operations such as modulo and division to extract digits or apply a mathematical formula. Therefore, it can be solved with simple integer variables.
The optimal approach uses the digital root property from number theory. Instead of repeatedly summing digits, you can compute the final single-digit result using a mathematical pattern based on modulo operations. This reduces the time complexity to constant time.
When digits are repeatedly summed, the result eventually converges to a value known as the digital root. This is a mathematical property of numbers in base 10. Recognizing this pattern allows you to derive the final answer directly without repeated digit summation.
The C# implementation builds on the efficient technique of digit root calculation using modulo arithmetic.