数的各位相加

今天做LeetCode的时候，发现这样一道题，是简单的题，不过有一点点奇特

题目让将一个数字的各位相加，出来的结果如果不是个位数，那么就再次相加，直到结果是个位数，这个个位数就是题目的结果

原题如下：

题目

最直接的想法是按照这个题意来，如果发现加出来的结果不是个位数，那就再加一遍，代码如下：

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

但是它题目下面还有一个要求：不使用循环和递归，并且在O(1)时间内完成（它写的是Follow up，我当做是必须的要求）

思考一下，应该是有什么规律，否则不可能实现这个要求的，所以写出了一部分数字，然后发现结果是1-9一直循环，所以将修改了代码：

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

提交了之后是正确的，但是我自己现在解释不了这个代码，所以还要再仔细研究一下这个规律

考虑两位数[10, 100)，他们各位数和的范围是1-18，假设它们都需要两遍和，第一遍数字范围1-18，第二遍变为1-9

第一遍：

每增加一个数，和也会增加1，假设sum(x)是x各位数的和，那么这时候sum(x+1) = sum(x)+1

较为特殊的是39到40，前者39 => 12， 后者40 => 4，其实是个位数减9，十位数加1，那么它们的各位和符合：sum(x+1) = sum(x) - 9 + 1

综合来说，第一遍有sum(x+1) = sum(x) + 1或者是sum(x+1) = sum(x) - 9 + 1两种情况

第二遍：

[1-18]这个范围内sum(x) = x % 9（当值为0的时候应该取值为9）成立

这样的话对于两位数sum(x+1) = (sum(x)+1) % 9或者是sum(x+1) = (sum(x)+1-9) % 9，对于后边这个式子，-9可以省略掉，所以合并之后就是

sum(x+1) = (sum(x) + 1) % 9 (当结果为0时，取值为9)

这是两位数的情况，三位数的话第一遍和的结果范围变为[1, 27]，第二遍范围[1, 18]，第三遍[1, 9]
...
12位，范围为[1, 108]，第二遍范围[1, 18]，第三遍[1, 9]
...

最终可以得出sum(x+1) = (sum(x) + 1) % 9 (当结果为0时，取值为9)可以一直成立下去

那么sum(x) = x % 9（结果为0时，取9）就是成立的，这就是我第二段代码的原理