Leetcode 258. Add Digits

Problem Explanation

The problem requires us to continuously add the digits of a given non-negative integer until we get a single digit as the result. For example, if the input is 38, we start by adding 3 and 8 to get 11, then 1 + 1 gives 2 which is a single digit number and therefore the result we are looking for.

Approach Explanation

The solution to this problem can be derived from a simple mathematical rule. If we analyze a series of numbers and the operation of adding their digits together until we get a single digit, we can notice a pattern. The result of this operation on these numbers corresponds to the numbers modulo 9 (remainder when divided by 9), except that for numbers that are multiples of 9 the result is 9, not 0. So based on this observation, we can simply return num mod 9 if num != 9*n, otherwise we return 9.

Walk through the example for the given algorithm:

Let's take an input number as 48. Our expectation would be to add the digits till it becomes a single digit.

4 + 8 = 12 --> 1 + 2 = 3

So, the output is 3.

Let’s see if our formula 1 + (num - 1) % 9 gives the same result.

Now, apply the formula:

1 + (48 - 1) % 9 = 1 + 47 % 9 = 1 + 2 = 3

Both the expected output and the output obtained from the formula are same, hence the formula is correct.

Python

1
2python
3class Solution:
4    def addDigits(self, num: int) -> int:
5        # If the number is 0, return 0
6        if num == 0:
7            return 0
8        # Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
9        return num % 9 if num % 9 != 0 else 9

Java

1
2java
3public class Solution {
4    public int addDigits(int num) {
5        // If the number is 0, return 0
6        if (num == 0) {
7            return 0;
8        }
9        // Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
10        return num % 9 == 0 ? 9 : num % 9;
11    }
12}

JavaScript

1
2javascript
3var addDigits = function(num) {
4    // If the number is 0, return 0
5    if (num === 0) {
6        return 0;
7    }
8    // Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
9    return num % 9 === 0 ? 9 : num % 9;
10};

C++

1
2c++
3class Solution {
4public:
5    int addDigits(int num) {
6        // If the number is 0, return 0
7        if (num == 0) {
8            return 0;
9        }
10        // Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
11        return num % 9 == 0 ? 9 : num % 9;
12    }
13};

C#

1
2csharp
3public class Solution {
4    public int AddDigits(int num) {
5        // If the number is 0, return 0
6        if (num == 0) {
7            return 0;
8        }
9        // Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
10        return num % 9 == 0 ? 9 : num % 9;
11    }
12}

Ruby

1
2ruby
3def add_digits(num)
4    # If the number is 0, return 0
5    if num == 0
6        return 0
7    end
8    # Otherwise, return num mod 9 if num isn't multiple of 9, else return 9
9    if num % 9 == 0
10        return 9
11    else
12        return num % 9
13    end
14end

Above, each solution we’ve provided is able to solve the problem by applying the mathematical rule we’ve established. That is, if a number is a multiple of 9, its sum of digits until a single digit is 9. For all other numbers, the sum of digits until a single digit equals that number modulo 9. This allows us to bypass the resource and time-intensive task of summing digits repeatedly, yet still solve the task at hand.

In terms of complexity, every solution runs in O(1) time complexity and uses O(1) space, as they perform a simple mathematical operation without relying on any looping or additional variables. This makes the solutions highly efficient for handling large integers, as the time and space requirements remain constant regardless of the input size.

To conclude, the problem of adding digits of a number until a single digit result is a great example of how important mathematical insight can be in solving coding tasks. The direct approach of repeatedly adding digits until reaching one digit can be improved dramatically by understanding the underlying mathematical patterns of the problem.