258. 各位相加

🟢   🔖  数学 数论 模拟  🔗 力扣 LeetCode

题目

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

Input: num = 38

Output: 2

Explanation: The process is

38 --> 3 + 8 --> 11

11 --> 1 + 1 --> 2

Since 2 has only one digit, return it.

Example 2:

Input: num = 0

Output: 0

Constraints:

• 0 <= num <= 231 - 1

Follow up: Could you do it without any loop/recursion in O(1) runtime?

题目大意

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

示例 1:

输入: num = 38

输出: 2

解释: 各位相加的过程为：38 --> 3 + 8 --> 11

11 --> 1 + 1 --> 2

由于 2 是一位数，所以返回 2。

示例 2:

输入: num = 0

输出: 0

提示：

• 0 <= num <= 231 - 1

进阶： 你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

解题思路

思路一：模拟逐步计算

1. 每次将数字的各位相加。
2. 如果结果仍然大于 9，继续重复此过程。
3. 当数字小于 10 时，返回结果。

复杂度分析

• 时间复杂度：O(log_10 n)，每次循环会减少一位数字。
• 空间复杂度：O(1)，只需要常量额外空间。

---

思路二：数学方法（数字根，O(1) 解法）

1. 数字根的概念（Digital Root）可用于快速找到结果：
   • 如果 num == 0，结果为 0。
   • 如果 num != 0，结果为 1 + (num - 1) % 9。
   • 公式来源：将数字 num 按照 10 进制分解后，可以得出其各位数字和对 9 取模的规律。
2. 使用公式直接计算，无需循环或递归。

复杂度分析

• 时间复杂度：O(1)，仅进行常数次数学运算。
• 空间复杂度：O(1)，不需要额外空间。

---

思路三：递归法

1. 如果 num 小于 10，直接返回。
2. 否则，将 num 的各位相加后递归调用自身。

复杂度分析

• 时间复杂度：O(log_10 n)，每次递归会减少一位数字。
• 空间复杂度：O(log_10 n)，递归调用栈的深度。

---

思路比较

方法	时间复杂度	空间复杂度	备注
模拟逐步相加	O(log_10 n)	O(1)	简单直观，代码可读性强
数学方法	O(1)	O(1)	最优解，高效且无需循环
递归法	O(log_10 n)	O(log_10 n)	简单实现，但递归耗费栈空间

代码

模拟逐步计算

var addDigits = function (num) {
	while (num >= 10) {
		let sum = 0;
		while (num > 0) {
			sum += num % 10; // 提取个位数并累加
			num = Math.floor(num / 10); // 去掉个位
		}
		num = sum;
	}
	return num;
};

数学方法

var addDigits = function (num) {
	if (num === 0) return 0;
	return 1 + ((num - 1) % 9);
};

递归法

var addDigits = function (num) {
	if (num < 10) return num;
	let sum = 0;
	while (num > 0) {
		sum += num % 10;
		num = Math.floor(num / 10);
	}
	return addDigits(sum);
};