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?

题目说到这份上，已经强烈暗示了可以不通过循环计算直接得到答案，那答案肯定是有规律的。所以让我们先来数个数：

0 -> 0

1 -> 1 2 ->2 … 8 -> 8 9 -> 9

10 -> 1 11 -> 2 … 17 -> 8 18 -> 9

19 -> 1 20 -> 2 … 26 -> 8 27 -> 9

28 -> 1 29 -> 2 … 35 -> 8 36 -> 9

到这里，我们可以发现，结果的变化规律。num的值总是在1～9之间逐渐变化，每次加1，到最后又归于1。所以，算法的代码如下：

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

当然，更加精简的写法如下：

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

这里，用了1 + (num - 1) % 9来代替条件判断。即使当num为0时，也有-1 % 9 = -1，还是可以得到正确结果。