Problem:

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?

此题最初想法是相加、判断反复循环直到找到满足的解。通过参考别人的解答发现，此题是让我们求“”。

由此解法一为通过循环相加判断，直到找到可行解：

class Solution {public:    int addDigits(int num)     {        int add = 0;         while (num >= 10)        {            while(num > 0)            {               add += num % 10;               num /= 10;            }            num = add;        }        return num;    }};

 

但是由于时间复杂度超过题目要求，故考虑针对“数根”的解法。

通过枚举可知：   

10 1+0 = 1

11 1+1 = 2

12 1+2 = 3    

13 1+3 = 4

14 1+4 = 5

15 1+5 = 6

16 1+6 = 7

17 1+7 = 8

18 1+8 = 9

19 1+9 = 1

20 2+0 = 2

于是可得出规律，每9个一循环。为处理9的倍数的情况，我们写为(n - 1) % 9 + 1。由此可得：

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