# 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 {
return (num == 0) ? 0 : (num - 1) % 9 + 1;
}
};

############

class Solution {
return (num - 1) % 9 + 1;
}
}

• // OJ: https://leetcode.com/problems/add-digits/
// Time: O(lgN)
// Space: O(1)
class Solution {
public:
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):
"""
: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
}
}