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 = ;

         while (num >= )

        {

            while(num > )

            {

               add += num % ;

               num /= ;

            }

            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 - ) %  + ;

    }

};