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?
題目分析：這道題讓我們求數(shù)根死姚，所謂樹根咬清，就是將大于10的數(shù)的各個位上的數(shù)字相加彪笼，若結(jié)果還大于0的話芹扭，則繼續(xù)相加盔粹，直到數(shù)字小于10為止
履婉。如果不看時間復(fù)雜度的話，直接按照字面解題用循環(huán)就可以宣羊。
public int addDigits(int num) {
int result = num;
while(result>=10){
result=result/10+result%10;
}
return result;
}
但是題目要求時間復(fù)雜度為O(1),所以肯定有個常數(shù)類型的公式來計算它璧诵。我們不妨列出一些數(shù)字和結(jié)果來找一下規(guī)律。
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
可以發(fā)現(xiàn)一個規(guī)律仇冯。這些數(shù)字每9個一循環(huán)之宿，可以看作所有數(shù)都是對9取余(9的倍數(shù)除外)。這樣寫出代碼如下
class Solution {
public int addDigits(int num) {
return (num-1) % 9 + 1;
}
}
