LeetCode 258. Add Digits

题目

同余定理，任何一个10进制数n 都可以表示成 n = a10^x + b10^(x-1) + .... c*10^0

那么 n ≡ ( a10^x + b10^(x-1) + .... c*10) mod 9

( a10^x + b10^(x-1) + .... c10) mod 9 = a10^x mod 9 + b * 10^(x-1) mod 9 +..c*10^0 mod9

又因为 a*10^x mod 9 = (a mod 9) * (10^x mod 9) = a mod 9

所以 n ≡ (a+b+..c) mod 9

题目求一个数字上每位上的数字相加得到一个新的数字，直到这个数字只有1位， 实际上就是 n ≡ (a+b+..c) ≡ n2 ≡ (a2+b2+..c2) ≡ ...nx ≡ (ax+bx+..cx) mod 9 其中 （nx = a(x-1)+b(x-1)+...c(x-1)）

所以求n对9的余数就好了。当余数为0是，答案输出9

class Solution {
public:
    int addDigits(int num) {
        
        if(num==0)
            return 0;
        return num%9==0?9:num%9;
        
    }
};