Problem Statement
Given a number, repeatedly add all its digits until the result becomes a single digit.
Example
-
Input: addDigits(38)
Output: 2
Explanation: ( 38 -> 3 + 8 = 11 -> 1 + 1 = 2 ).
-
Input: addDigits(123)
Output: 6
Explanation: ( 123 -> 1 + 2 + 3 = 6 ).
-
Input: addDigits(0)
Output: 0
Brute Force Approach
Approach
Idea: Use a loop to calculate the sum of the digits of the number. Continue the process until the number becomes a single digit.
Steps
- Initialize a while loop that runs as long as the number has more than one digit.
- Within the loop, calculate the sum of the digits of the number.
- Replace the number with the calculated sum.
- Return the final single-digit number.
Time & Space Complexity
- Time Complexity: O(d), where
d is the number of digits in the number.
- The loop runs until the number becomes a single digit.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: num = 38
- First iteration:
- Calculate
3 + 8 = 11.
- Update
num = 11.
- Second iteration:
- Calculate
1 + 1 = 2.
- Update
num = 2.
- Exit loop and return
2.
Efficient Approach Using Mathematical Properties
Approach
Idea: Use the digital root property of numbers. The result can be calculated using the formula: num = 1 + (num - 1) % 9
This formula works because the sum of the digits of a number modulo 9 is equivalent to the number modulo 9.
Steps
- Handle the special case where
num = 0. Return 0.
- Apply the formula
num = 1 + (num - 1) % 9.
- Return the result.
Time & Space Complexity
- Time Complexity: O(1)
- The operation is constant-time.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: num = 38
- Check if
num = 0: No.
- Apply the formula:
1 + (38 - 1) % 9 = 1 + 37 % 9 = 1 + 1 = 2.
- Return
2.
Complexity Analysis
| Operation | Brute Force | Efficient Approach |
|---|
| Time Complexity | O(d) | O(1) |
| Space Complexity | O(1) | O(1) |
Conclusion
- The brute force approach provides an intuitive way to calculate the result but involves multiple iterations to sum the digits.
- The efficient approach leverages mathematical properties to compute the result in constant time.
- This problem demonstrates how understanding mathematical insights can lead to highly optimized solutions.