0258. Add Digits ================ 题目信息 -------- :题号: 0258 :难度: Easy :主题: 数学、十进制数位、数字根 :原题: `LeetCode 0258 `_ :重点: 重复计算十进制数位和、结果必须缩减到单个数字、``0`` 的边界语义 题目重述 -------- 给定一个非负整数 ``num``,反复把它的十进制各位数字相加,并用所得总和替代原数,直到当前值只剩一个十进制数字,返回这个最终数字。 ``num`` 位于 ``[0, 2^31 - 1]``。当输入本来就是一位数时直接返回它;特别地,``0`` 的结果仍为 ``0``。题目的进阶要求是思考能否不使用循环或递归,以常数时间完成计算,但返回结果的定义不因此改变。 自建示例 -------- 需要进行两轮数位求和: .. code-block:: text 输入:num = 9998 输出:8 解释:第一轮得到 9 + 9 + 9 + 8 = 35,第二轮得到 3 + 5 = 8;8 已经是一位数。 零值边界: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { public: int addDigits(int num) { if (num == 0) return 0; return 1 + (num - 1) % 9; } }; 代码分析 -------- 公式把原本可能多轮的过程压缩为常数次运算,时间复杂度和额外空间均为 ``O(1)``。 输入是非负整数,因此 ``num-1`` 只在正数分支执行,不会形成负数边界问题。