题目描述

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

样例

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

进阶

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

算法1

(模拟) $O(\log n)$

1. 直接按照题目所说的模拟。

时间复杂度

• 时间复杂度和数位相关，第二次迭代数字就会最多变为两位数，故时间复杂度为$O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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

算法2

(数论) $O(1)$

1. 只需要判断这个数字模 9 之后的余数（若余 0 则返回 9）。
2. 可以证明 $num = \sum_{k=0}^{n-1}10^k \cdot x_k$ 与 $\sum_{k=0}^{n-1}x_k$ 在模 9 的意义下同余，故可以直接用这个数字模 9 的余数作为答案。

时间复杂度

• 只有一次运算，故时间复杂度为 $O(1)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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