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