各位相加如何用数字根做到 O(1)？（LeetCode 258）

简化版

反复把各位数字相加，最后得到一位数，这个结果叫数字根。除 0 外，答案可以用公式 1 + (num - 1) % 9 得到；如果 num == 0，答案是 0。

详细版

模拟写法：

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

数学写法：

int addDigits(int num) {
    return num == 0 ? 0 : 1 + (num - 1) % 9;
}

数学公式来自十进制下 10 ≡ 1 (mod 9)，所以一个数与它的各位数字和对 9 同余。

完整版教学

一、什么是数字根

把一个数的各位反复相加，直到只剩一位：

38 -> 3 + 8 = 11
11 -> 1 + 1 = 2
答案 2

这个最终一位数就是数字根。

二、为什么和 9 有关系

十进制数可以写成：

abc = a * 100 + b * 10 + c

因为：

100 ≡ 1 (mod 9)
10  ≡ 1 (mod 9)

所以：

abc ≡ a + b + c (mod 9)

每次各位相加都不会改变它对 9 的余数。

三、数字根公式怎么来

非零数字的数字根范围是 1..9，而普通取模结果范围是 0..8。所以要把余数 0 映射成 9。

num	num % 9	数字根
`18`	`0`	`9`
`38`	`2`	`2`
`9`	`0`	`9`
`0`	`0`	`0`

公式 1 + (num - 1) % 9 正好完成这个映射。

记忆钩子：数字根是“模 9 但没有 0 档”，所以非零时把结果平移到 1 到 9。

四、为什么 0 要单独处理

如果直接套公式：

1 + (0 - 1) % 9

不同语言对负数取模结果不一致，而且数学意义上 0 的数字根就是 0。单独判断最清楚。

五、模拟法什么时候有用

如果面试官不要求 O(1)，模拟法更直观；如果题目明确要求“不使用循环”，才需要数字根公式。

while (num >= 10) {
    // 求数位和
}

模拟法也有助于解释公式不是魔法，而是把反复数位和压缩成同余关系。

六、复杂度比较

模拟法每轮处理若干位，数字会快速变小，复杂度可以写作 O(log n)；数学公式是 O(1)。

空间复杂度两者都是 O(1)。

七、常见误区与追问

误区：直接返回 num % 9。 9、18、27 的数字根应是 9，不是 0。
误区：忘记单独处理 0。 0 的数字根是 0，不是 9。
误区：把公式当作只适用于两位数。 它来自十进制权重对 9 同余，任意位数都成立。
追问：为什么 10 对 9 同余为 1？ 因为 10 = 9 + 1，高位权重都会退化成 1。
追问：其他进制怎么办？ b 进制下对应模 b-1。
追问：复杂度是多少？ 公式法 O(1)，模拟法 O(log n)。

八、加强记忆

各位相加最终值就是数字根。口诀是：num == 0 返回 0，否则返回 1 + (num - 1) % 9。不要写成 num % 9，因为数字根的 9 对应余数 0。

简化版

详细版