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
Use a while loop to repeatedly sum the digits of the number until we get a single digit.
Algorithm
- While number is greater than 9 (has more than one digit):
- Initialize sum as 0
- While number is greater than 0:
- Add the last digit (num % 10) to sum
- Remove the last digit (num /= 10)
- Set number to sum
- Return the final single digit
Walkthrough
In this approach, we use a while loop that continues as long as the number has more than one digit (num > 9). In each iteration, we extract each digit using the modulo operator (%) and integer division (/), and add them together. This process continues until we get a single digit.
public int addDigits(int num) { while (num > 9) { int sum = 0; while (num > 0) { sum += num % 10; num /= 10; } num = sum; } return num;}Complexity
Time
O(log n) - where n is the input number, as we need to process each digit
Space
O(1) - only using constant extra space
Trade-offs
Pros
Easy to understand and implement
Works for all positive integers
Straightforward logic
Cons
Not the most efficient solution
Uses loops which might not be optimal
Time complexity depends on the number of digits
Use recursion to sum the digits until we get a single digit number.
Algorithm
- If number is less than 10, return the number
- Calculate sum of digits:
- While number is greater than 0:
- Add the last digit to sum
- Remove the last digit
- While number is greater than 0:
- Recursively call function with sum
Walkthrough
This approach uses recursion to solve the problem. We first calculate the sum of digits, and if the sum is greater than 9, we recursively call the function with the sum as the new input.
public int addDigits(int num) { if (num < 10) return num; int sum = 0; while (num > 0) { sum += num % 10; num /= 10; } return addDigits(sum);}Complexity
Time
O(log n) - where n is the input number, as we need to process each digit
Space
O(log n) - due to recursive call stack
Trade-offs
Pros
Clean and elegant solution
Easy to understand the logic
Code is more concise
Cons
Uses recursion which consumes stack space
Not as space efficient as iterative solution
Still not the most optimal solution
Solutions
Solution
class Solution {public int addDigits(int num) { return (num - 1) % 9 + 1; }}class Solution {public: int addDigits(int num) { return (num - 1) % 9 + 1; }};class Solution: def addDigits( self, num: int) -> int: return 0 if num == 0 else (num - 1) % 9 + 1Video 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.