readme.md

258、各位相加

tag: python 、 数学

---

题目描述

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

示例

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

进阶:

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

---

题目链接

258. 各位相加

---

题解

• 循环法

  最简单直观的方法，每次循环累加数的各个位数，并替代当前值，直到求和结果小于 10 为止。

  class Solution:
      def addDigits(self, num: int) -> int:
          while num >= 10:
              num = sum([int(x) for x in str(num)])
          return num

  最终结果，运行时间36ms，超过68.98%；占用内存13.4MB，超过15.63%。

• 公式法

  题目提示我们可以在 O(1) 的时间复杂度下完成，那么显然这可以找到规律或是直接使用一个数学表达式得到最终结果。那么我们观察数 num 可以表示为 ai * 10^i 的累加和，其中 i 表示 [1, num的位数] 。它是和 ai 的累加和对 9 是同余的，那么我们设题目要求的目标为函数 f(x)，则 f(x)≡x(mod 9)，则 f(f(x))≡f(x)≡x(mod 9)那么可以得到最终的结果和 9 是同余的，又由于在 num=9 时需要令 f(x)=9 而不是 0，将式子变为 1 + (x - 1) % 9，这时又由于 num=0 的情况，所以最终式子为 (1 + (x - 1) % 9) * int(num != 0)。

  class Solution:
      def addDigits(self, num: int) -> int:
          return (1 + (num - 1) % 9) * int(num != 0)

  最终结果，运行时间36ms，超过68.98%；占用内存13.4MB，超过15.63%。最终结果竟然和有循环的方法一样，很震惊。