Facebook Pixel

258. Add Digits

EasyMathNumber TheorySimulation
Leetcode Link

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 add 3 + 8 = 11, then add 1 + 1 = 2. Since 2 is a single digit, return 2.
  • If num = 123, first add 1 + 2 + 3 = 6. Since 6 is already a single digit, return 6.

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 returns 0

This formula directly computes the result without actually performing the repeated digit additions, making it an O(1) time complexity solution.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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: subtracting 1, taking modulo, then adding 1 back gives the correct digit
  • For multiples of 9: this formula correctly returns 9
  • 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:

  1. Special Case Check: First, we handle the edge case where num == 0. If the input is 0, we directly return 0 since there's no need for calculation.

  2. 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 of 9 don't incorrectly map to 0.
    • Modulo 9: (num - 1) % 9 gives us a value between 0 and 8.
    • Add 1: Adding 1 back shifts the range to 1 through 9, which are the valid single digits we want.

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 Evaluator

Example 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 (since 46 = 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 (since 26 = 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
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More