题目描述

[EN | CN]

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

示例:

1
2
3
输入: 38
输出: 2
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。

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

解法 1:尾递归

顺着题意递归即可。

复杂度分析略。

实现与结果如下:

1
2
3
class Solution:
    def addDigits(self, num: int) -> int:
        return num if num < 10 else self.addDigits(sum([int(i) for i in str(num)]))
  • 执行用时:40 ms,在所有 Python3 提交中击败了 78.43% 的用户。
  • 内存消耗:13.4 MB,在所有 Python3 提交中击败了 8.70% 的用户。

解法 2:数学

思考一下对一个数进行一次这样的操作的本质是什么?

假如对于一个数字 $29$,各位之和是 $11$,再计算一次各位之和又变成 $2$,在这个过程中实际上是将原来的一个进位 $10$ 变成了一个 $1$,减少了 $9$。因此,其实我们再继续进行的「求各位之和」操作就相当于每次都去掉原来的「各位之和」若干个 $9$ 直到得到个位数,即 各位之和对 $9$ 取余

更进一步的是,对于一个数 $k\times 10^n$,它对 $9$ 取余的结果等于 $k$ 对 $9$ 取余的结果,即 $k \times 10^n \mod 9 = k \mod 9$。

综上,对于非负整数 $N$ 来说,对它求各位之和直到得到个位数的结果,相当于用它对 $9$ 取余。不过这里还要注意一个地方,如果一个数刚好是 9 的倍数,那么它的结果应该是 9 而不是 1,因此公式上应该写成 $$ (N - 1) \mod 9 + 1 $$ 复杂度分析略。

实现与结果如下:

1
2
3
class Solution:
    def addDigits(self, num: int) -> int:
        return (num - 1) % 9 + 1 if num != 0 else 0
  • 执行用时:40 ms,在所有 Python3 提交中击败了 78.43% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 8.70% 的用户。