Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, 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?

这道题的本质就是求数根(digital root)，直接求的方法很简单，使用循环直接按照要求让num小于10就可以了，如果使用O(1)的时间复杂度当然不能这样做了。

分析如下：11的数根是2，2+9=11，为什么加了9之后就相等了呢，因为2+9进了1位，相当于十位从0变为1，但是个位减了1，从2变为了1。加上9的效果就是从个位减1 十位加1，这样就抵消了，所以数根相同。因此可知一个数，若为个位数，你们数根为其本身；若不是个位数，那么数根为该数mod 9到一个个位数（比如18，mod9==0，明显它的数根是9，因此需要用一个方式避免这种情况）

麻烦一点：

1 class Solution { 2 public: 3     int addDigits(int num) { 4         if(num<=9) 5         { 6             return num; 7         } 8         else 9         {10             int a=num%9;11             if(a==0)12             {13                 return 9;14             }15             else16             {17                 return a;18             }19         }20     }21 };

嘿嘿这个有点麻烦呢。。

怎么把他简单一点呢，直接这样就可以啦，

return (1 + (num-1) % 9);

这样就可以避免18,27.....这种情况啦

 

参考：

[1]https://en.wikipedia.org/wiki/Digital_root