給定一個非負(fù)整數(shù) num，反復(fù)將各個位上的數(shù)字相加，直到結(jié)果為一位數(shù)。

示例:

輸入: 38
輸出: 2
解釋: 各位相加的過程為：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位數(shù)，所以返回 2。

進(jìn)階:
你可以不使用循環(huán)或者遞歸，且在 O(1) 時間復(fù)雜度內(nèi)解決這個問題嗎？

解法二 數(shù)學(xué)上
看了下 Discuss ，原來要求的數(shù)叫做數(shù)字根，看下 維基百科 的定義。

在數(shù)學(xué)中，數(shù)根(又稱位數(shù)根或數(shù)字根Digital root)是自然數(shù)的一種性質(zhì)，換句話說，每個自然數(shù)都有一個數(shù)根。

數(shù)根是將一正整數(shù)的各個位數(shù)相加（即橫向相加），若加完后的值大于10的話，則繼續(xù)將各位數(shù)進(jìn)行橫向相加直到其值小于十為止[1]，或是，將一數(shù)字重復(fù)做數(shù)字和，直到其值小于十為止，則所得的值為該數(shù)的數(shù)根。

例如54817的數(shù)根為7，因為5+4+8+1+7=25，25大于10則再加一次，2+5=7，7小于十，則7為54817的數(shù)根。

然后是它的用途。

數(shù)根可以計算模運算的同余，對于非常大的數(shù)字的情況下可以節(jié)省很多時間。

數(shù)字根可作為一種檢驗計算正確性的方法。例如，兩數(shù)字的和的數(shù)根等于兩數(shù)字分別的數(shù)根的和。

另外，數(shù)根也可以用來判斷數(shù)字的整除性，如果數(shù)根能被3或9整除，則原來的數(shù)也能被3或9整除。

接下來討論我們怎么求出樹根。

我們把 1 到 30 的樹根列出來。

原數(shù): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
數(shù)根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
可以發(fā)現(xiàn)數(shù)根 9 個為一組， 1 - 9 循環(huán)出現(xiàn)。我們需要做就是把原數(shù)映射到樹根就可以，循環(huán)出現(xiàn)的話，想到的就是取余了。

結(jié)合上邊的規(guī)律，對于給定的 n 有三種情況。

n 是 0 ，數(shù)根就是 0。

n 不是 9 的倍數(shù)，數(shù)根就是 n 對 9 取余，即 n mod 9。

n 是 9 的倍數(shù)，數(shù)根就是 9。

我們可以把兩種情況統(tǒng)一起來，我們將給定的數(shù)字減 1，相當(dāng)于原數(shù)整體向左偏移了 1，然后再將得到的數(shù)字對 9 取余，最后將得到的結(jié)果加 1 即可。

原數(shù)是 n，樹根就可以表示成 (n-1) mod 9 + 1，可以結(jié)合下邊的過程理解。

原數(shù): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
偏移: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
取余: 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2
數(shù)根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
所以代碼的話其實一句就夠了。

public int addDigits(int num) {
return (num - 1) % 9 + 1;
}

public class Solution {
    public int AddDigits(int num) {
        int res = num;
        while(num >= 10){
            res = 0;
            while(num > 0){
                res += num % 10;
                num /= 10;
            }
            num = res;
        }
        return res;
    }
}