258. 各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

本题用循环来解决本题实在很简单，根据题意去循环即可。
代码如下:

class Solution {
    public int addDigits(int num) {
        int n = num;
        while( n / 10 > 0){

            int sum = 0;
            while( n > 0){
                sum += n % 10;
                n /= 10;
            }
            n = sum;
        }
        return n;
    }
}

但是本题的要求还有是要不用循环或者递归，时间复杂度是O(1)，就是常数时间复杂度，这就让我有点摸不着头脑了，难道可以不将各位数求出来，就能得到答案吗？
我想了想如果有的话，就一定是直接通过数字的值去得到答案，可以用一个公式去得到。其实我是想放弃了，因为知道个公式并没有太大意义。
结果自己就试了试罗列一下100-110

• 100 101 102 103 104 105 106 107 108 109 110
• 1 2 3 4 5 6 7 8 9 1 2

罗列到这里发现后面也不用罗列了，因为后面就是一直循环1-9这个过程，那显然就是取余了，但是由于取余得到的结果其实0-取余数-1，而这个循环是1-9那就是取余数是9，然后结果在+1即可。
由于 0 % 9 + 1 = 1 1 % 9 + 1= 2 因此非常自然的将数字-1再取余就是答案了。

那公式就是 ( num - 1 ) % 9 + 1
试试看

image.png

OK，那公式就出来了，本题也就结束了。
本题通过进阶的提示，告诉我们肯定是直接通过数值来求解，那不妨来罗列些数字找找规律，找规律的难度几乎可以说是没有，因此本题的难点主要在于你是否想到罗列数字。如果想到了，那本题也就迎刃而解了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。