LeetCode Notes: Add Digits

#leetcode

Question

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

Example 1:

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.

Example 2:

Input: num = 0

Output: 0

Constraints:

  • 0 <= num <= 231 - 1

Follow up: Could you do it without any loop/recursion in O(1) runtime?

Solution One

Analysis:

First of all, I thought of recursively calculating the sum of the numbers in each digit, until the number less than or equal to 9 is found.

Code:

/**
  * @param {number} num
  * @return {number}
  */
var addDigits = function(num) {
     // Split each number into an array
     num = (''+num).split('')
     // Use the reduce method of the array to easily calculate the sum of numbers
     const sum = num.reduce((pre,cur)=>{
         // +pre + +cur is equivalent to (+pre) + (+cur):
         // +pre and +cur will convert pre and cur into numbers, and then add them
         return +pre + +cur
     })
     if(sum> 9){
         // The sum is greater than 9 and continue to recursively calculate the sum
         return addDigits(sum)
     }else{
         // find successful
         return sum
     }
};

Solution Two

Analysis:

Let's first enumerate the results within 20

Number: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Result: 0 1 2 3 4 5 6 7 8 9 1  2  3  4  5  6  7  8  9  1  2  ...

It can be observed that in addition to the initial 0, the results are cycled in accordance with 1-9. After 9 is 1, we try to take the remainder of 9, and find that the remainder is the result we want. The only difference is that when the remainder is 0 (a multiple of 9), the result should be 9 directly.

Code:

/**
  * @param {number} num
  * @return {number}
  */
var addDigits = function(num) {
     // Special case 0, return directly
     if(num === 0) return 0
     // Get the remainder of 9
     const n = num% 9
     // If it is a multiple of 9, directly return 9
     // If not, return the remainder
     return n === 0? 9: n;
};

Solution Three

Analysis:

The above scheme can be simplified, because when we take the remainder of 9 to get 0, we need to use 9 as the return value. This situation requires special treatment. Can we make a conversion to make the remainder 0 compatible with other situations? We try to shift num one place to the left (num-1) and take the remainder of 9.

Number:                0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Offset (num-1):       -1 0 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 17 18 19 ...
Remainder (num-1)% 9: -1 0 1 2 3 4 5 6 7 8 0  1  2  3  4  5  6  7  8  0  1  ...
Result:                0 1 2 3 4 5 6 7 8 9 1  2  3  4  5  6  7  8  9  1  2  ...

It can be seen that the difference between (num-1)% 9 and the final result value is only 1, and it is also compatible with the case where num is 0.

Code:

/**
  * @param {number} num
  * @return {number}
  */
var addDigits = function(num) {
     // num is shifted by one bit to the left and then takes the remainder of 9, 
     // and the remainder is +1 to unify the multiples of 9 and the numbers that are not multiples into an algorithm
     return (num-1)% 9 + 1
};

Reference

Comments