Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/258.html

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?

Algorithm

Let’s first observe all the roots from 1 to 20:

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

Draw a rule, every 9 a cycle, all roots of numbers greater than 9 take the remainder of 9, so for the number equal to 9 to take the remainder of 9 is 0, in order to get itself, and also need to be greater than The number of 9 applies, we use the expression (n-1)%9+1 to cover all cases.

There is another special case that needs to be considered. When num is 0, then there will be a situation of -1% 9, need to make an additional judgment.

Code

  • class Solution {
      public int addDigits(int num) {
              return (num == 0) ? 0 : (num - 1) % 9 + 1;
          }
    };
    
    
    ############
    
    class Solution {
        public int addDigits(int num) {
            return (num - 1) % 9 + 1;
        }
    }
    
  • // OJ: https://leetcode.com/problems/add-digits/
    // Time: O(lgN)
    // Space: O(1)
    class Solution {
    public:
        int addDigits(int n) {
            while (n > 9) {
                int next = 0;
                for (; n; n /= 10) next += n % 10;
                n = next;
            }
            return n;
        }
    };
    
  • class Solution:
        def addDigits(self, num: int) -> int:
            return 0 if num == 0 else (num - 1) % 9 + 1
    
    ############
    
    class Solution(object):
      def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num < 10:
          return num
        return 1 + (num - 1) % 9
    
    
  • func addDigits(num int) int {
    	if num == 0 {
    		return 0
    	}
    	return (num-1)%9 + 1
    }
    
  • impl Solution {
        pub fn add_digits(mut num: i32) -> i32 {
            (num - 1) % 9 + 1
        }
    }
    
    

All Problems

All Solutions