[数据结构与算法][每日一题]158：各位相加

题目描述

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

示例 1:

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

示例 2:

输入: num = 0
输出: 0

提示：

• 0 <= num <= 2³¹ - 1

题解思路

方法一：模拟

最直观的方法是模拟各位相加的过程，直到剩下的数字是一位数。

计算一个整数的各位相加的做法是，每次计算当前整数除以 10 的余数得到最低位数，将最低位数加到总和中，然后将当前整数除以 10。重复上述操作直到当前整数变成 0，此时的总和即为原整数各位相加的结果。

代码如下：

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

复杂度分析

• 时间复杂度：$O(lognum)$，其中 num 是给定的整数。对于 num 计算一次各位相加需要 $O(lognum)$ 的时间，由于 num≤2³¹ ?1，因此对于 num 计算一次各位相加的最大可能结果是 82，对于任意两位数最多只需要计算两次各位相加的结果即可得到一位数。

• 空间复杂度：O(1)。

方法二：数学

假设整数 num 的十进制表示有 n 位，从最低位到最高位依次是 a₀ 到 a_n?1，则 num 可以写成如下形式：

当 i = 0 时，10ⁱ - 1 = 0 是 9 的倍数；当 i 是正整数时，10ⁱ - 1 是由 i 位 9 组成的整数，也是 9 的倍数。因此对于任意非负整数 i，10ⁱ - 1 都是 9 的倍数。由此可得num 与其各位相加的结果模 9 同余。重复计算各位相加的结果直到结果为一位数时，该一位数即为 num 的数根，num 与其数根模 9 同余。

我们对 num 分类讨论：

• num 不是 9 的倍数时，其数根即为 num 除以 9 的余数。
• num 是 9 的倍数时：
  • 如果 num=0，则其数根是 0；
  • 如果 num>0，则各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。

细节：

根据上述分析可知，当 num>0 时，其数根的结果在范围 [1,9] 内，因此可以想到计算num?1 除以 9 的余数然后加 1。由于当 num>0 时，num?1≥0，非负数除以 9 的余数一定也是非负数，因此计算 num?1 除以 9 的余数然后加 1 的结果是正确的。

当 num=0 时，num?1=?1<0，负数对 9 取余或取模的结果的正负在不同语言中有所不同。

对于取余的语言，结果的正负和左操作数相同，则 num?1 对 9 取余的结果为 ?1，加 1 后得到结果 0，可以得到正确的结果；

对于取模的语言，结果的正负和右操作数相同，则 num?1 对 9 取模的结果为 8，加 1 后得到结果 9，无法得到正确的结果，此时需要对 \num=0 的情况专门做处理。

代码如下：

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

复杂度分析

• 时间复杂度：O(1)。

• 空间复杂度：O(1)。