简单

问题描述

给定一个非负整数 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) 时间复杂度内解决这个问题吗？

模拟

按题意模拟。

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  let ans = num
    .toString()
    .split('')
    .reduce((sum, n) => sum + +n, 0)
  while (ans > 9) {
    ans = addDigits(ans)
  }
  return ans
}

• 时间复杂度：$O(log\;num)$
• 空间复杂度：$O(1)$

数学

数学上，这道题是求给出的数的数根 (opens new window)

对于某个 $n$ 位的十进制整数 $num$，假设从最低位到最高位依次是 $a_0, a_1, \dots, a_{n-1}$，那么这个数可以表示为：

$$num = \sum_{i=0}^{n-1} a_i \times 10^i$$

显然 $10^i\;\text{mod}\;9 = 1$，因此可得：

$$num\;\text{mod}\;9 = \sum_{i=0}^{n-1} a_i\;\text{mod}\;9$$

记 $f(x) = \sum_{i=0}^{n-1} a_i\;\text{mod}\;9$，那么 $f(x) = x\;\text{mod}\;9$，那么 $f(f(x)) = (x\;\text{mod}\;9)\;\text{mod}\;9 \equiv x\;\text{mod}\;9$，但是数根的取值范围是 $[1,9]$，对 $9$ 取余的取值范围为 $[0,8]$，可以先将给定的数字减 $1$，相当于原数整体向左偏移了 $1$，然后再将得到的数字对 $9$ 取余，最后将得到的结果加 $1$。

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  return ((num - 1) % 9) + 1
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$