258. 各位相加

题目

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

示例 1:

输入: num = 38
输出: 2
解释: 各位相加的过程为：
38 —> 3 + 8 —> 11
11 —> 1 + 1 —> 2
由于 2 是一位数，所以返回 2。
示例 1:

输入: num = 0
输出: 0

提示：

0 <= num <= 231 - 1

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

思路

最笨的办法肯定是按题意模拟，要写两个循环，时间复杂度和的位数相关，是级别。

想能不能每两位相加后立马再加一次，只保留末位个位数，试了一下也是可以的，比如输入，先加最末尾两位和，得到，的和相加得到，和相加得到，的和得到，加得到，的和得到，结果和8+7+4+9->28->10->1是一样的。这样只需要一个循环，但复杂度还是一样的。

关于常数时间内求解，确实想不到。评论区的这个解释很明了：#card=math&code=X%20%3D%20100%2Aa%20%2B%2010%2Ab%20%2B%20c%20%3D%2099%2Aa%20%2B%209%2Ab%20%2B%20%28a%2Bb%2Bc%29&id=RNHpx)，所以对取余即可。不过如果大于且余数是，要返回。

代码

O(logn)

class Solution {
    public int addDigits(int num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num /= 10;
            // 这里ans每次算完都是一个10以内的数
            ans = ans % 10 + ans / 10;
        }
        return ans;
    }
}

O(1)

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