数字各位相加直到结果为一位数

数字各位相加直到结果为一位数

问题描述

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数，返回最终结果。

示例：
输入：38 → 3+8=11 → 1+1=2 → 输出：2

方法一：循环迭代法

class Solution {
    // 时间复杂度 O(logn)  空间复杂度 O(1)
    public int addDigits(int num) {
        while (num >= 10) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
}

算法思路：
通过双重循环实现：

1. 外层循环控制当前数值是否需要继续计算
2. 内层循环完成一次位数求和
3. 当数值小于10时终止循环

方法二：数学公式法（数根公式）

class Solution {
    // 时间复杂度 O(1)  空间复杂度 O(1)
    public int addDigits(int num) {
        if (num == 0) return 0;
        return num % 9 == 0 ? 9 : num % 9;
    }
}

数学原理：
数根(Digital Root)公式推导：

• 任何数可以表示为：num = a₀ + a₁10 + a₂100 + …
• 由于 10 ≡ 1 (mod 9)，因此 num ≡ sum(a₀ + a₁ + a₂ + …) (mod 9)
• 特殊情况处理：num为0时直接返回0，能被9整除的非零数返回9

方法三：递归解法

class Solution {
    // 时间复杂度 O(logn)  空间复杂度 O(logn)（递归栈）
    public int addDigits(int num) {
        if (num < 10) return num;
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return addDigits(sum);
    }
}

进阶解法：位运算优化

class Solution {
    // 时间复杂度 O(1)  空间复杂度 O(1)
    public int addDigits(int num) {
        return num - 9 * ((num - 1) / 9);
    }
}

原理说明：
通过数学变形实现的位运算优化，等价于数根公式，但避免了条件判断。例如：

• 当 num=38 → (38-1)/9=4 → 38 - 9*4 = 2
• 当 num=18 → (18-1)/9=1 → 18 - 9*1 = 9

复杂度对比

总结

对于算法题，推荐优先使用数学公式法，其具有最优的时间和空间复杂度。在面试场景中，可以先用循环迭代法展示思路，再引出数学公式法展示算法优化能力。