Add Digits

Difficulty: Easy | Acceptance: 68.90% | Paid: No Topics: Math, Simulation, Number Theory

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

• Examples
• Constraints
• Simulation Loop
• Mathematical Formula (Digital Root)

Examples

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.

Input: num = 0
Output: 0

Constraints

0 <= num <= 2³¹ - 1

Simulation Loop

Intuition We can directly simulate the process described in the problem statement. We repeatedly extract digits, sum them up, and replace the number with this sum until the number is small enough (less than 10).

Steps

• While the number is greater than or equal to 10:
  • Initialize a temporary sum variable to 0.
  • While the number is greater than 0:
    • Add the last digit (num % 10) to the sum.
    • Remove the last digit (num // 10 or integer division).
  • Update the number to be the calculated sum.
• Return the final number.

class Solution:
    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

Complexity

• Time: O(log n) - In the worst case, we process the digits of the number, and the number shrinks rapidly.
• Space: O(1) - We only use a few variables for storage.
• Notes: This approach is intuitive but involves a loop, which is less efficient than the mathematical constant-time solution.

Mathematical Formula (Digital Root)

Intuition This problem is a classic application of the “Digital Root” concept from number theory. The digital root of a number is the value obtained by an iterative process of summing digits until a single-digit number is achieved. There is a known congruence formula for this: dr(n) = 1 + (n - 1) % 9 for n > 0. This works because numbers are congruent modulo 9 to the sum of their digits.

Steps

• Handle the edge case where num is 0 (return 0).
• If the number is divisible by 9, the digital root is 9 (unless the number is 0).
• Otherwise, the digital root is the remainder when divided by 9.
• This can be simplified to: return 0 if num is 0, otherwise return 1 + (num - 1) % 9.

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        return 1 + (num - 1) % 9

Complexity

• Time: O(1) - Mathematical operations are performed in constant time.
• Space: O(1) - No extra space is used.
• Notes: This is the optimal solution for this problem, leveraging mathematical properties to avoid loops entirely.