LeetCode算法解题集：Add Digits

题目：
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?

思路：
按照提示，去 wiki 看了下这个算法 Digital root，排列一部分数据，得出原始数-最大9的整数倍，即为目标值。算法复杂度 O(1)!!!!!!

代码：

class Solution 
{
public:
    int addDigits(int num) 
    {
        if( num <= 9 )
        {
            return num;
        }
        int nTargetNum = num / 9;
        int nResult = num - nTargetNum * 9;
        return nResult > 0 ? nResult : 9;
    }
};

总结：
1、思路很重要，看到题目的竟然想到的是记录每个数位上的值，这样算法复杂度不知道要高多少倍了
2、临界值！没有无bug的程序，只有未找到的边界值，多想想边界值。
3、提交了3次才通过，很惭愧！