Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
题目分析：这道题让我们求数根，所谓树根，就是将大于10的数的各个位上的数字相加，若结果还大于0的话，则继续相加，直到数字小于10为止
。如果不看时间复杂度的话，直接按照字面解题用循环就可以。
public int addDigits(int num) {
int result = num;
while(result>=10){
result=result/10+result%10;
}
return result;
}
但是题目要求时间复杂度为O(1),所以肯定有个常数类型的公式来计算它。我们不妨列出一些数字和结果来找一下规律。
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
可以发现一个规律。这些数字每9个一循环，可以看作所有数都是对9取余(9的倍数除外)。这样写出代码如下
class Solution {
public int addDigits(int num) {
return (num-1) % 9 + 1;
}
}
