Add Digits
EasyPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
Use the concept of digital root in mathematics to solve the problem in O(1) time without any loops or recursion.
Algorithm
- If number is 0, return 0
- If number is divisible by 9, return 9
- Otherwise, return number mod 9
Walkthrough
This approach uses the mathematical concept of digital root. For a non-zero number num, its digital root is congruent to num mod 9. If num is divisible by 9, the digital root is 9, else it's num mod 9. For zero, the digital root is 0.
public int addDigits(int num) { if (num == 0) return 0; if (num % 9 == 0) return 9; return num % 9;}Complexity
Time
O(1) - constant time operation regardless of input size
Space
O(1) - only using constant extra space
Trade-offs
Pros
O(1) time complexity
No loops or recursion needed
Most efficient solution
Constant space complexity
Cons
Requires understanding of digital root concept
Might be less intuitive at first glance
Could be harder to explain in an interview setting
Solutions
Solution
class Solution {public int addDigits(int num) { return (num - 1) % 9 + 1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.