0258. Add Digits

题目信息

题号:

0258

难度:

Easy

主题:

数学、十进制数位、数字根

原题:

LeetCode 0258

重点:

重复计算十进制数位和、结果必须缩减到单个数字、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 只在正数分支执行,不会形成负数边界问题。