Code Implementation

class Solution:
    def addDigits(self, num: int) -> int:
        # Digital root formula for base 10
        if num == 0:
            return 0
        else:
            return 1 + (num - 1) % 9
      

class Solution {
public:
    int addDigits(int num) {
        if (num == 0) return 0;
        else return 1 + (num - 1) % 9;
    }
};
      

class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0;
        else return 1 + (num - 1) % 9;
    }
}
      

var addDigits = function(num) {
    if (num === 0) return 0;
    else return 1 + ((num - 1) % 9);
};
      

Problem Description

You are given a non-negative integer num. Your task is to repeatedly add all its digits until the result has only one digit, then return that single-digit result.

• You must perform the digit addition iteratively: after each sum, if the result has more than one digit, repeat the process.
• For example, if num = 38, you compute 3 + 8 = 11, then 1 + 1 = 2, so the answer is 2.
• The input num is a non-negative integer (i.e., num ≥ 0).
• Your solution should be efficient and not use recursion or loops if possible.

Thought Process

At first glance, this problem seems to require repeatedly summing the digits of num until only one digit remains. The most direct approach is to use a loop: extract each digit, sum them, and repeat until the number is a single digit. However, the problem hints at finding a more efficient solution, possibly without explicit iteration.

Upon further thought, this process is related to a mathematical concept called the "digital root." The digital root of a number is the value obtained by an iterative process of summing its digits until a single-digit number is produced. There is a well-known formula for computing the digital root in base 10, which can give us the answer in constant time.

The challenge is to recognize this mathematical shortcut and apply it, moving from a brute-force, iterative solution to an elegant, O(1) time solution.

Solution Approach

Let's break down the steps to solve this problem, starting with the brute-force method and then explaining the optimized approach.

• Brute-force method:
  • While num has more than one digit, do the following:
  • Initialize sum = 0.
  • Extract each digit from num (using num % 10), add it to sum, and remove the digit from num (using integer division by 10).
  • Once all digits are summed, set num = sum and repeat.
  • When num is a single digit, return it.
• Optimized method (Digital Root):
  • Mathematically, the digital root of a number in base 10 can be found using the formula: 1 + (num - 1) % 9 (except for num = 0, where the result is 0).
  • This formula works because every time you sum digits, you are effectively reducing the number modulo 9.
  • So, for any num greater than 0, the answer is 1 + (num - 1) % 9.
  • This approach gives you the result in constant time, with no loops or recursion.

We use the optimized method for its clarity and efficiency.

Example Walkthrough

Let's use num = 38 as an example:

1. First iteration: 3 + 8 = 11
2. Second iteration: 1 + 1 = 2
3. Now 2 is a single digit, so we return 2.

Using the digital root formula:

• 1 + (38 - 1) % 9 = 1 + 37 % 9 = 1 + 1 = 2
• The answer matches the iterative process, confirming the formula is correct.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(log n), where n is the input number. Each pass reduces the number of digits, and each digit is processed in each pass.
  • Space Complexity: O(1), since only a few variables are used.
• Optimized Approach (Digital Root):
  • Time Complexity: O(1), because the answer is computed with a simple arithmetic formula, regardless of the size of num.
  • Space Complexity: O(1), since only a constant number of variables are used.

Summary

The "Add Digits" problem can be solved by simulating the digit-summing process, but recognizing its mathematical structure allows us to use the digital root formula for an elegant, constant-time solution. This insight transforms a potentially iterative task into a direct computation, making the solution both efficient and concise.