258. 各位相加
题目描述
输入一个非负整数 num。
把它每一位上的数字加起来得到一个新数。只要新数还不止一位，就继续这样做。
返回最后得到的那个一位数。
示例 1
输入：num = 38 输出：2
解释：3 + 8 = 11，再算 1 + 1 = 2，2 只有一位，返回 2。
示例 2
输入：num = 0 输出：0
解释：0 本来就是一位数。
数据范围
0 <= num <= 2^31 - 1
进阶：能否不用循环和递归，在 O(1) 时间内得出结果？
解题思路：模拟
直接模拟：只要 num 还不是一位数，就用取余和整除把它的各位拆出来相加，用和替换 num。进阶观察：一个数和它的各位和模 9 同余，所以答案也可以直接写成 num = 0 时为 0，否则为 1 + (num - 1) % 9。
为什么正确
每轮替换前后，num 模 9 的余数不变。
复杂度分析
模拟法每轮 O(位数)，第一轮后数字就不超过 90，总体约 O(log num)；公式法 O(1)。空间 O(1)。
易错点
循环条件是 num >= 10 而不是 num > 10，否则 10 会被直接返回。用公式时要单独处理 0，并注意 9 的倍数答案是 9 不是 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addDigits(self, num: int) -> int:
while num >= 10:
total = 0
while num:
total += num % 10
num //= 10
num = total
return numclass Solution {
public int addDigits(int num) {
while (num >= 10) {
int total = 0;
while (num != 0) {
total += num % 10;
num /= 10;
}
num = total;
}
return num;
}
}class Solution {
public:
int addDigits(int num) {
while (num >= 10) {
int total = 0;
while (num) {
total += num % 10;
num /= 10;
}
num = total;
}
return num;
}
};func addDigits(num int) int {
for num >= 10 {
total := 0
for num != 0 {
total += num % 10
num /= 10
}
num = total
}
return num
}var addDigits = function(num) {
while (num >= 10) {
let total = 0;
while (num) {
total += num % 10;
num = Math.floor(num / 10);
}
num = total;
}
return num;
};function addDigits(num: number): number {
while (num >= 10) {
let total = 0;
while (num) {
total += num % 10;
num = Math.floor(num / 10);
}
num = total;
}
return num;
}其他解法
模拟按题意重复求各位数字和；数根公式利用模 9 不变直接算出结果，不需要循环。
解法 2：数根公式 时间 O(1)，空间 O(1)
因为 10 ≡ 1 (mod 9)，一个数和它的各位数字之和模 9 同余，反复相加不改变模 9 的余数。最终结果在 1–9 之间（num = 0 时为 0），所以答案是 1 + (num - 1) % 9。
一行式 O(1)，满足进阶要求。需要知道同余性质，并处理 num = 0 和 9 的倍数这两个边界。
class Solution:
def addDigits(self, num: int) -> int:
return 0 if num == 0 else 1 + (num - 1) % 9class Solution {
public int addDigits(int num) {
return num == 0 ? 0 : 1 + (num - 1) % 9;
}
}class Solution {
public:
int addDigits(int num) {
return num == 0 ? 0 : 1 + (num - 1) % 9;
}
};func addDigits(num int) int {
if num == 0 {
return 0
}
return 1 + (num-1)%9
}var addDigits = function(num) {
return num === 0 ? 0 : 1 + (num - 1) % 9;
};function addDigits(num: number): number {
return num === 0 ? 0 : 1 + (num - 1) % 9;
}