Armstrong Number
如果一个正整数等于它的各位数字分别取其位数次幂后相加的和，它就是阿姆斯特朗数。153有三位，且1^3 + 5^3 + 3^3 = 153，所以它是阿姆斯特朗数。编写一个函数，接收n，如果它是阿姆斯特朗数就返回true，否则返回false。
函数
- ninteger
- 要测试的正整数
- 返回值boolean
- 当 n 等于各位数字分别自乘位数次后所得结果的总和时为 true
约束条件
1 ≤ n ≤ 109
示例
- 输入
- n = 153
- 输出
- true
- 解释
153有 3 位数，因此每一位都要立方：1 + 125 + 27 = 153。总和等于原来的数字，所以答案是true。
- 输入
- n = 10
- 输出
- false
- 解释
10有 2 位数字，所以每位数字都要平方：1 + 0 = 1，结果不是10。答案是false。
- 输入
- n = 9474
- 输出
- true
- 解释
- 对于 4 位数字，幂是 4：
6561 + 256 + 2401 + 256 = 9474，结果就是这个数字，因此答案是true。
进阶
在 1 和 10^9 之间只有 31 个阿姆斯特朗数。你能不逐个测试 10 亿个数字，把它们全部列出来吗？
提示
逐个打开提示，每个都会多透露一点。
在将一个数字提升到某个次方之前，你需要知道指数。
n有几位数？你如何通过算术运算找出答案？n % 10是最后一位数字，除以 10 的整数除法会将它去掉。重复这个过程，直到没有数字剩下：这样就会遍历每一位数字，步骤数就是指数k。一次循环统计数字的位数。然后再次逐位提取数字，将每一位数字的
k次方加到一个 64 位总和中，并返回总和是否等于原始的n。
题解
定义就是这个算法：统计 n 的位数，将每一位都提升到这个次数，再把结果相加，并与 n 比较。指数是这个 n 的位数，不是固定的 3，而且总和可能超出 32 位整数的范围：999999999 会得到 9 × 9^9 = 3486784401。
从字符串中读取数字
思路
n 的十进制字符串包含了你需要的两项信息：它的长度就是指数 k，它的字符就是各个数字。对于 9474，你要计算 9^4 + 4^4 + 7^4 + 4^4。当且仅当总和等于 n 时，n 才是 Armstrong 数。
用 k 次乘法计算一个幂，每个数字需要 k 步，因此检查的复杂度是 O(k²)，其中 k 大约是 log n：这里最多需要 100 次乘法。
算法
- 将
n转换为十进制字符串，并令k为它的长度。 - 将 64 位的
total设为0。 - 对于每个字符，将它转换为数字
d，并将d^k加到total中，使用整数相乘，而不是调用浮点数幂函数。 - 返回
total是否等于n。
def isArmstrong(n):
digits = str(n)
k = len(digits)
total = 0
for ch in digits:
total += int(ch) ** k
return total == n拆分数字，并查找它们的幂
思路
这种算术方法不需要字符串。m % 10 是 m 的最后一位数字，整除 10 会去掉这一位，所以不断相除直到没有剩余，就能统计数字的位数：9474 变成 947、94、9、0，因此 k = 4。
只有 10 个数字，所以先为从 0 到 9 的 d 构建 powers[d] = d^k。这样每个数字只需查找一次，而不是进行 k 次乘法：时间复杂度为 O(log n)，空间复杂度为 O(1)。
每一项都是零或正数，所以总和一旦超过 n，答案就是 false。对于 999999999，三位数字相加后就会超过，此时 3 × 387420489 = 1162261467。
算法
- 将
n的副本不断除以 10，直到结果变为 0，统计数字个数，并将其记为k。 - 对从 0 到 9 的每个数字
d，将powers[d] = d^k存入 64 位整数。 - 再将
n的一个新副本除以 10，每一步都将powers[m % 10]加到total上。 - 如果
total大于n，立即返回false。 - 处理完最后一位数字后，返回
total是否等于n。
def isArmstrong(n):
# Count the digits: k is the exponent.
k = 0
m = n
while m > 0:
k += 1
m //= 10
# powers[d] = d^k for the ten possible digits.
powers = [d ** k for d in range(10)]
total = 0
m = n
while m > 0:
total += powers[m % 10]
if total > n:
return False # the total only grows
m //= 10
return total == n
易错点和边界情况
- 指数固定为 3。它接受
153和370，但会拒绝9474以及所有大于 1 的一位数，因为7^3 = 343。 - 32 位求和。
999999999的各位数字的和为3486784401，对于n = 10^9，表格中的条目9^10也是同一个数。C 会溢出并导致未定义行为，Java 和 C# 会回绕为负数，而 Rust 调试版会触发 panic。 - 浮点数幂运算。某些 C 运行时曾对
pow(5, 2)返回24.999...，转换为整数时会截断为24。请改用整数相乘。 - 与错误的值进行比较。数字循环会将
n除到 0，因此请对副本进行操作。 - R 中的科学计数法。
as.character(1e9)的结果是"1e+09"，共 5 个字符；请用sprintf("%.0f", n)格式化。
常见问题3
什么是阿姆斯特朗数？
阿姆斯特朗数也叫自恋数，它等于自身各位数字分别升至数字位数次方后的总和。9474 就是一个阿姆斯特朗数，因为 9^4 + 4^4 + 7^4 + 4^4 = 9474。每个一位数都符合条件，因为 d^1 = d。
有多少个阿姆斯特朗数？
在十进制中，恰好有 88 个正整数各位数字的幂之和等于它本身，其中最大的有 39 位。这个列表是有限的，因为一个 k 位数至少是 10^(k-1)，而它各位数字的幂之和最多是 k × 9^k。从 61 位开始，各位数字的幂之和就无法赶上这个数。
检查一个阿姆斯特朗数的时间复杂度是多少？
n 大约有 log n 位数字，这里最多为 10 位。逐个剥离数字，并在一个包含 10 个元素的表中查找每个幂次，时间复杂度为 O(log n)，空间复杂度为 O(1)。对每个数字都用循环重新计算 d^k，会使时间复杂度变为 O(log² n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isArmstrong(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 153
预期输出
true