258. Add Digits
Problem Description
Given an integer num
, you need to repeatedly add all its digits together until only a single digit remains, then return that single digit.
For example:
- If
num = 38
, first add3 + 8 = 11
, then add1 + 1 = 2
. Since2
is a single digit, return2
. - If
num = 123
, first add1 + 2 + 3 = 6
. Since6
is already a single digit, return6
.
The solution uses a mathematical property called the digital root. The digital root of a positive integer can be calculated using the formula (num - 1) % 9 + 1
. This works because:
- Numbers that are multiples of 9 have a digital root of 9
- Other numbers have a digital root equal to their remainder when divided by 9
- The special case of
0
returns0
This formula directly computes the result without actually performing the repeated digit additions, making it an O(1) time complexity solution.
Intuition
To understand why the formula (num - 1) % 9 + 1
works, let's first observe patterns when we repeatedly add digits.
Consider what happens with different numbers:
10 → 1 + 0 = 1
11 → 1 + 1 = 2
12 → 1 + 2 = 3
- ...
18 → 1 + 8 = 9
19 → 1 + 9 = 10 → 1 + 0 = 1
20 → 2 + 0 = 2
Notice a pattern? After 18
(which gives 9
), the number 19
cycles back to 1
. This happens because adding digits is related to finding the remainder when dividing by 9
.
The key insight comes from how numbers work in base 10. Any number can be written as:
num = d₀ × 10⁰ + d₁ × 10¹ + d₂ × 10² + ...
Since 10 ≡ 1 (mod 9)
, we have 10ⁿ ≡ 1 (mod 9)
for any n. This means:
num ≡ d₀ + d₁ + d₂ + ... (mod 9)
So the sum of digits has the same remainder as the original number when divided by 9
. Repeatedly summing digits doesn't change this remainder, eventually leading us to a single digit.
The tricky part is handling multiples of 9
. While num % 9
would give 0
for multiples of 9
, we actually want 9
as the result (since 9
is a valid single digit). This is why we use (num - 1) % 9 + 1
:
- For non-multiples of
9
: subtracting1
, taking modulo, then adding1
back gives the correct digit - For multiples of
9
: this formula correctly returns9
- For
0
: we handle it as a special case
Solution Approach
The solution implements the digital root formula in a single line. Let's break down the implementation:
def addDigits(self, num: int) -> int:
return 0 if num == 0 else (num - 1) % 9 + 1
The algorithm works as follows:
-
Special Case Check: First, we handle the edge case where
num == 0
. If the input is0
, we directly return0
since there's no need for calculation. -
Digital Root Formula: For all other numbers, we apply the formula
(num - 1) % 9 + 1
:- Subtract 1:
num - 1
shifts the number range. This ensures that multiples of9
don't incorrectly map to0
. - Modulo 9:
(num - 1) % 9
gives us a value between0
and8
. - Add 1: Adding
1
back shifts the range to1
through9
, which are the valid single digits we want.
- Subtract 1:
Examples walkthrough:
- For
num = 38
:(38 - 1) % 9 + 1 = 37 % 9 + 1 = 1 + 1 = 2
- For
num = 9
:(9 - 1) % 9 + 1 = 8 % 9 + 1 = 8 + 1 = 9
- For
num = 18
:(18 - 1) % 9 + 1 = 17 % 9 + 1 = 8 + 1 = 9
- For
num = 19
:(19 - 1) % 9 + 1 = 18 % 9 + 1 = 0 + 1 = 1
This approach achieves:
- Time Complexity: O(1) - just a single arithmetic operation
- Space Complexity: O(1) - no extra space needed
The beauty of this solution is that it avoids the iterative process entirely by leveraging the mathematical property of digital roots.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with num = 47
:
Using the iterative approach (to understand what we're calculating):
- First iteration:
4 + 7 = 11
- Second iteration:
1 + 1 = 2
- Result:
2
Using our O(1) formula approach:
Given num = 47
, we apply the formula: (num - 1) % 9 + 1
Step 1: Check if num == 0
47 ≠ 0
, so we proceed with the formula
Step 2: Subtract 1 from the number
47 - 1 = 46
Step 3: Take modulo 9
46 % 9 = 1
(since46 = 9 × 5 + 1
)
Step 4: Add 1 back
1 + 1 = 2
Result: 2
Let's verify with another example where num = 27
(a multiple of 9):
Step 1: Check if num == 0
27 ≠ 0
, so we proceed
Step 2: Subtract 1
27 - 1 = 26
Step 3: Take modulo 9
26 % 9 = 8
(since26 = 9 × 2 + 8
)
Step 4: Add 1 back
8 + 1 = 9
Result: 9
(correctly returns 9 for a multiple of 9)
The formula elegantly handles all cases: regular numbers map to their digital root (1-9), multiples of 9 correctly return 9, and 0 returns 0.
Solution Implementation
1class Solution:
2 def addDigits(self, num: int) -> int:
3 """
4 Calculate the digital root of a non-negative integer.
5 The digital root is obtained by iteratively summing digits until a single digit remains.
6
7 Mathematical property: The digital root of a positive number follows the pattern:
8 - If num == 0, result is 0
9 - If num % 9 == 0 (and num != 0), result is 9
10 - Otherwise, result is num % 9
11
12 This can be expressed as: (num - 1) % 9 + 1 for positive numbers
13
14 Args:
15 num: A non-negative integer
16
17 Returns:
18 The digital root (single digit from 0-9)
19 """
20 # Special case: if number is 0, return 0
21 if num == 0:
22 return 0
23
24 # For positive numbers, use the mathematical formula
25 # Subtracting 1 before modulo and adding 1 after ensures:
26 # - Numbers divisible by 9 return 9 (not 0)
27 # - Other numbers return their correct digital root (1-8)
28 return (num - 1) % 9 + 1
29
1class Solution {
2 /**
3 * Computes the digital root of a non-negative integer.
4 * The digital root is obtained by iteratively summing all digits
5 * until a single digit remains.
6 *
7 * Mathematical insight: The digital root follows a pattern based on modulo 9:
8 * - If num == 0, result is 0
9 * - If num % 9 == 0 (and num != 0), result is 9
10 * - Otherwise, result is num % 9
11 *
12 * The formula (num - 1) % 9 + 1 elegantly handles all cases:
13 * - Maps multiples of 9 to 9 instead of 0
14 * - Preserves the modulo 9 value for all other numbers
15 * - Special case: when num is 0, returns 0 (since -1 % 9 + 1 = 0)
16 *
17 * @param num The non-negative integer to process
18 * @return The digital root (single digit sum) of the input number
19 */
20 public int addDigits(int num) {
21 // Handle edge case explicitly for clarity
22 if (num == 0) {
23 return 0;
24 }
25
26 // Apply the digital root formula
27 // Subtract 1 to shift the range, apply modulo 9, then add 1 back
28 // This ensures multiples of 9 return 9 instead of 0
29 return (num - 1) % 9 + 1;
30 }
31}
32
1class Solution {
2public:
3 /**
4 * Finds the digital root of a number (repeatedly add digits until single digit remains)
5 *
6 * Mathematical property: The digital root of a positive integer follows a pattern:
7 * - If num == 0, result is 0
8 * - If num % 9 == 0 (and num != 0), result is 9
9 * - Otherwise, result is num % 9
10 *
11 * This can be simplified to: (num - 1) % 9 + 1 for all positive integers
12 *
13 * @param num The input non-negative integer
14 * @return The single digit result after repeatedly adding all digits
15 */
16 int addDigits(int num) {
17 // Handle special case when num is 0
18 if (num == 0) {
19 return 0;
20 }
21
22 // Apply the digital root formula
23 // Subtracting 1 shifts the range, mod 9 gives remainder, adding 1 adjusts back
24 // This ensures multiples of 9 return 9 instead of 0
25 return (num - 1) % 9 + 1;
26 }
27};
28
1/**
2 * Finds the digital root of a number (repeatedly add digits until single digit remains)
3 *
4 * Mathematical property: The digital root of a positive integer follows a pattern:
5 * - If num == 0, result is 0
6 * - If num % 9 == 0 (and num != 0), result is 9
7 * - Otherwise, result is num % 9
8 *
9 * This can be simplified to: (num - 1) % 9 + 1 for all positive integers
10 *
11 * @param num - The input non-negative integer
12 * @returns The single digit result after repeatedly adding all digits
13 */
14function addDigits(num: number): number {
15 // Handle special case when num is 0
16 if (num === 0) {
17 return 0;
18 }
19
20 // Apply the digital root formula
21 // Subtracting 1 shifts the range, mod 9 gives remainder, adding 1 adjusts back
22 // This ensures multiples of 9 return 9 instead of 0
23 return (num - 1) % 9 + 1;
24}
25
Time and Space Complexity
Time Complexity: O(1)
The solution uses a mathematical formula based on the digital root property. The expression (num - 1) % 9 + 1
performs a constant number of operations regardless of the input size:
- One subtraction operation:
num - 1
- One modulo operation:
% 9
- One addition operation:
+ 1
- One comparison operation:
num == 0
These operations are executed in constant time, independent of the magnitude of num
.
Space Complexity: O(1)
The algorithm uses only a fixed amount of extra space:
- No additional data structures are created
- No recursive calls that would use stack space
- Only the input parameter
num
and the return value are stored
The space usage remains constant regardless of the input value.
Common Pitfalls
1. Forgetting the Special Case for Zero
A common mistake is applying the formula (num - 1) % 9 + 1
directly to all inputs without checking for zero first.
Incorrect Implementation:
def addDigits(self, num: int) -> int:
return (num - 1) % 9 + 1 # Wrong for num = 0
Problem: When num = 0
, this returns (0 - 1) % 9 + 1 = -1 % 9 + 1 = 8 + 1 = 9
, which is incorrect. The digital root of 0 should be 0.
Solution: Always handle zero as a special case:
def addDigits(self, num: int) -> int:
return 0 if num == 0 else (num - 1) % 9 + 1
2. Using the Wrong Formula: num % 9
Another frequent error is using num % 9
directly without the adjustment.
Incorrect Implementation:
def addDigits(self, num: int) -> int:
return num % 9 if num % 9 != 0 else 9 # Works but more complex
Problem: While this can work with additional conditional logic, it requires handling multiples of 9 separately, making the code more complex and error-prone.
Solution: Use the formula (num - 1) % 9 + 1
which elegantly handles all positive cases including multiples of 9.
3. Implementing the Iterative Approach When O(1) is Required
Some might implement the literal interpretation of the problem by repeatedly summing digits.
Inefficient Implementation:
def addDigits(self, num: int) -> int:
while num >= 10:
digit_sum = 0
while num > 0:
digit_sum += num % 10
num //= 10
num = digit_sum
return num
Problem: This has O(log n) time complexity and misses the mathematical insight that enables O(1) solution.
Solution: Recognize the digital root pattern and use the mathematical formula for constant time complexity.
4. Negative Number Handling
Though the problem typically specifies non-negative integers, forgetting to consider negative inputs can cause issues.
Potential Issue:
def addDigits(self, num: int) -> int:
# What happens with num = -38?
return 0 if num == 0 else (num - 1) % 9 + 1
Problem: Negative numbers would give unexpected results. For example, -38
would return ((-38 - 1) % 9 + 1) = (-39 % 9 + 1) = 6
, which might not be the intended behavior.
Solution: If negative numbers are possible, add validation or handle them explicitly:
def addDigits(self, num: int) -> int:
if num < 0:
# Handle negative case based on requirements
# Option 1: Work with absolute value
num = abs(num)
return 0 if num == 0 else (num - 1) % 9 + 1
Which data structure is used to implement priority queue?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!