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.

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.

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

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