digital root

這道題【https://leetcode.com/problems/add-digits/】自己寫的答案代碼：

public int addDigits(int num) {

        if(num/9 == 0){

            return num;

        }

        if(num%9 == 0){

            return 9;

        }

        return num%9;

    }

主要是根據提示看了相關數根的知識，證明見下：

轉載保留版權：http://haipz.com/blog/i/6456 - 海胖部落格

數根是自然數的一種性質，換句話說，每個自然數都有一個數根。數根是将一正整數的各個位數相加(即橫向相加)，若加完後的值大于10的話，則繼續将各位數進行橫向相加直到其值小于十為止，或是，将一數字重複做數字和，直到其值小于十為止，則所得的值為該數的數根。

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

公式法求數根：

a的數根b = ( a - 1) % 9 + 1

另外還有一個結論要記：任何一個整數模9同餘于它的各數位上數字之和。

具體證明過程如下：

設自然數N=a[n]a[n-1]…a[0]，其中a[0]，a[1]、…、a[n]分别是個位、十位、…上的數字

再設M=a[0]+a[1]+…+a[n]

求證：N≡M(mod 9). 

證明：

因為 N=a[n]a[n-1]…a[0]=a[n]*10^n+a[n-1]*10^(n-1)+…+a[1]*10+a[0]

又因為 1≡1(mod 9), 10≡1(mod 9), 10^2≡1(mod 9), … 10^n≡1(mod 9)

上面這些同餘式兩邊分别同乘以a[0]、a[1]、a[2]、…、a[n]，再相加得：

a[0]+a[1]*10+…+a[n]*10^n≡(a[0]+a[1]+…+a[n])(mod 9)， 即 N≡M(mod 9)，得證。