Sum of Digits

Q: 对一个数字的各位数字求和的时间复杂度是多少？

每位数字处理一步，所以是 O(d) ，其中 d 是数字的位数。数字 n 大约有 log10(n) + 1 位，因此这个复杂度通常也写作 O(log n) 。对于 32 位整数，最多需要 10 步。

Q: 一个数的数字根是什么？

它是把各位数字反复相加，直到只剩一位数后得到的结果： 9045 得到 18，然后得到 9。对于正数 n ，它等于 1 + (n-1) % 9 ，因为任何数除以 9 的余数，都和它的各位数字之和除以 9 的余数相同。

Q: 字符串版本还是算术版本更好？

两种方法的时间复杂度都是 O(d) ，而且都正确。字符串版本在许多语言中更短，但会创建一份数字的副本。算术版本只使用 O(1) 的额外内存，还能体现你了解 % 10 和 / 10 如何拆分一个数字。这一点在回文和数字反转问题中也会用到。

入门数学与模拟

+10

给你一个非负整数 n。返回它的十进制各位数字之和。例如，482 的各位数字是 4、8 和 2，因此答案是 14。

函数

sumOfDigits(n: integer) → integer

ninteger: 你要相加各位数字的非负整数
返回值integer: n 的各位数字之和

约束条件

0 ≤ n ≤ 2³¹-1

示例

输入: n = 9045
输出: 18
解释: 9045 的各位数字是 9、0、4 和 5，且 9 + 0 + 4 + 5 = 18。零不增加任何数值，但仍然算作一位数字。

输入: n = 7
输出: 7
解释: 一位数的各位数字之和就是它本身，所以 7 的结果是 7。

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

每次拆出一位数字。你可以读取它的十进制文本，也可以用 n % 10 取出最后一位，再用 10 做整数除法将其去掉。两种方法都需要为每一位执行一步，这里用 d 表示位数，且 d ≤ 10。算术方法不需要额外的内存。

将数字作为文本读取

思路

把 n 转成十进制文本，这样 9045 就会变成字符 9、0、4 和 5，然后把每个字符的值相加。

字符还不是数字。字符 '4' 存储为代码 52，所以你可以解析它，或者减去 '0' 的代码：'4' - '0' = 4。数字字符的代码是连续的，因此这种减法对全部十个数字都有效。

循环需要 O(d) 时间，文本需要 O(d) 的额外空间。

算法

将 n 转换为十进制文本。
将 total = 0 赋给 total。
对于每个字符，将它的数字值加到 total 中。
返回 total。

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

用 % 10 取出最后一位数字

思路

除以 10 的余数就是最后一位数字：9045 % 10 = 5。将数字除以 10 并取整，就会去掉这一位：当小数部分被舍去时，9045 / 10 = 904。重复这两个步骤，数字就会从右向左依次取出。

对于 9045：加上 5，保留 904；加上 4，保留 90；加上 0，保留 9；加上 9，保留 0。循环在 0 处停止，总和为 18。对于 n = 0，循环不会运行，答案为 0。

共有 d 步，内存中只有两个整数：时间复杂度为 O(d)，空间复杂度为 O(1)。每个中间值都小于 n，因此不会溢出。

算法

将 total = 0。
当 n > 0 时，将 n % 10 加到 total 中。
将 n 除以 10，并舍去小数部分。
当 n 变为 0 时，返回 total。

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

易错点和边界情况

在会进行实数除法的语言中使用 /。在 JavaScript、TypeScript、Lua、PHP 和 R 中，9045 / 10 的结果是 904.5，循环会累加小数。使用 Math.floor 或 math.floor 向下取整；在 Python 中使用 //，在 Dart 中使用 ~/，在 PHP 中使用 intdiv，在 R 中使用 %/%。
累加字符而不是数字。字符 '7' 的编码是 55，而不是 7。
在 n >= 10 时继续循环。最高位数字会留在 n 中，没有被累加，所以 9045 的结果是 9，而不是 18。
在 R 中将大数字转换为文本。as.character(100000) 的结果是 "1e+05"；请使用 format(n, scientific = FALSE)。

常见问题3

对一个数字的各位数字求和的时间复杂度是多少？

每位数字处理一步，所以是 O(d)，其中 d 是数字的位数。数字 n 大约有 log10(n) + 1 位，因此这个复杂度通常也写作 O(log n)。对于 32 位整数，最多需要 10 步。

一个数的数字根是什么？

它是把各位数字反复相加，直到只剩一位数后得到的结果：9045 得到 18，然后得到 9。对于正数 n，它等于 1 + (n-1) % 9，因为任何数除以 9 的余数，都和它的各位数字之和除以 9 的余数相同。

字符串版本还是算术版本更好？

两种方法的时间复杂度都是 O(d)，而且都正确。字符串版本在许多语言中更短，但会创建一份数字的副本。算术版本只使用 O(1) 的额外内存，还能体现你了解 % 10 和 / 10 如何拆分一个数字。这一点在回文和数字反转问题中也会用到。

def sumOfDigits(n):
    # 在这里编写代码

测试 #1

测试 #2

参数

n = 9045

预期输出