日野弥生：勉強しよう

LeetCode 258 - 各位相加

发表于2025年05月06日

用递归法模拟相加的过程可以得到答案。但是这需要O(log(num))的栈空间。

class Solution:
    def addDigits(self, num: int) -> int:
        first = num // 10
        second = num % 10
        if first + second >= 10:
            return self.addDigits(first + second)
        return first + second
            

数学方法

数根与模 9 同余的数学证明

假设整数 num 的十进制表示有 $n$ 位，从最低位到最高位依次是 $a_0$ 到 $a_{n−1}$，则 num 可以写成如下形式：

我们可以将其进一步拆分为：

当 $i=0$ 时，$10^i - 1 = 0$，是 9 的倍数；
当 $i$ 是正整数时，$10^i - 1$ 是由 $i$ 位 9 组成的整数，也是 9 的倍数。

因此对于任意非负整数 $i$，$10^i - 1$ 都是 9 的倍数。

由此可得：

$\text{num}$ 与其各位相加的结果在模 9 意义下同余。

换句话说，反复将一个数的各位数字相加，最终会得到一个与原数模 9 同余的一位数，这个结果就被称为该数的 数根（digital root）。

对 num 分类讨论

1. 当 num 不是 9 的倍数时，其数根即为 num 除以 9 的余数： \(\text{数根} = \text{num} \mod 9\)

2. 当 num 是 9 的倍数时：

   • 如果 num = 0，则其数根是 0；
   • 如果 num > 0，则其各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。

数根总结公式

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        if num % 9 == 0:
            return 9
        return (num) % 9