0258. Add Digits¶
题目信息¶
- 题号:
0258
- 难度:
Easy
- 主题:
数学、十进制数位、数字根
- 原题:
- 重点:
重复计算十进制数位和、结果必须缩减到单个数字、
0的边界语义
题目重述¶
给定一个非负整数 num,反复把它的十进制各位数字相加,并用所得总和替代原数,直到当前值只剩一个十进制数字,返回这个最终数字。
num 位于 [0, 2^31 - 1]。当输入本来就是一位数时直接返回它;特别地,0 的结果仍为 0。题目的进阶要求是思考能否不使用循环或递归,以常数时间完成计算,但返回结果的定义不因此改变。
自建示例¶
需要进行两轮数位求和:
输入:num = 9998
输出:8
解释:第一轮得到 9 + 9 + 9 + 8 = 35,第二轮得到 3 + 5 = 8;8 已经是一位数。
零值边界:
输入:num = 0
输出:0
解释:0 已经是单个十进制数字,不需要继续求和。
数字根与模 9¶
十进制数的各位和与原数模 9 同余,因为 10 ≡ 1 (mod 9)。反复求位和不会改变这个余数,
直到结果落在 0 到 9 的一位数字中:
num=0时最终结果为 0;正数的数字根在 1 到 9 之间,余数为 0 时对应 9,其他余数直接对应自身。
所以正数的结果是 1 + (num - 1) % 9。这不是把数字 0 误解释为 9 的普通 num%9,
num=0 必须单独处理。
正确性说明¶
设一次位和转换为 f(x)。由十进制展开式,f(x) ≡ x (mod 9);重复转换保持同一余数,
而每次多位数转换都会显著减小,最终必到一位数。正数最终一位数字只能是 1..9,
其模 9 余数唯一确定结果,得到上述公式;零从一开始就是最终状态。
C++ 实现¶
class Solution {
public:
int addDigits(int num) {
if (num == 0) return 0;
return 1 + (num - 1) % 9;
}
};
代码分析¶
公式把原本可能多轮的过程压缩为常数次运算,时间复杂度和额外空间均为 O(1)。
输入是非负整数,因此 num-1 只在正数分支执行,不会形成负数边界问题。