Armstrong Number
正の整数は、自身の各桁を桁数乗した値の合計と等しいとき、アームストロング数です。153は3桁で、1^3 + 5^3 + 3^3 = 153なので、アームストロング数です。nを受け取り、アームストロング数ならtrue、そうでなければfalseを返す関数を書いてください。
関数
- ninteger
- テストする正の整数
- 戻り値boolean
- n が、各桁を桁数乗した値の合計に等しい場合は true
制約
1 ≤ n ≤ 109
例
- 入力
- n = 153
- 出力
- true
- 説明
153は3桁なので、各桁を3乗します：1 + 125 + 27 = 153。合計すると元の数になるので、答えはtrueです。
- 入力
- n = 10
- 出力
- false
- 説明
10は2桁なので、各桁を2乗します：1 + 0 = 1となり、10ではありません。答えはfalseです。
- 入力
- n = 9474
- 出力
- true
- 説明
- 4桁の場合、べき乗は4です。
6561 + 256 + 2401 + 256 = 9474となり、元の数と同じなので、答えはtrueです。
提出時に隠しテスト+31件
発展問題
1 と 10^9 の間には、アームストロング数がわずか 31 個しかありません。10億個の数を1つずつ調べずに、すべて列挙できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数字を累乗するには、まず指数が必要です。
nは何桁の数字でしょうか？また、算術を使ってどうすればそれを求められるでしょうか？n % 10は最後の桁で、10による整数除算でそれを取り除きます。何も残らなくなるまで繰り返します。これによりすべての桁を調べられ、ステップ数が指数kになります。1回の走査で桁数を数えます。次に、もう一度桁を取り出し、各桁を
k乗した値を64ビットの合計に加え、その合計が元のnと等しいかどうかを返します。
解説
定義はアルゴリズムです。nの桁数を調べ、各桁をその桁数乗し、結果を合計してnと比較します。注意すべき点は数値にあります。指数は固定の3ではなく、このnの桁数です。また、合計は32ビット整数の範囲を超えることがあります。999999999の場合は9 × 9^9 = 3486784401です。
文字列から数字を読み取る
考え方
nの10進文字列から、必要なものが両方わかります。文字列の長さが指数kで、各文字が数字です。9474の場合、文字列は4文字なので、9^4 + 4^4 + 7^4 + 4^4を足します。
各文字を数字に戻し、k乗して累計に加えます。計算が終わった時点で合計がnと等しい場合に限り、nはアームストロング数です。
合計は64ビット整数に格納します。nは32ビットに収まりますが、合計はそうとは限りません。999999999の場合、3486784401となり、32ビットの上限2147483647を超えます。k回の乗算を行うループでべき乗を計算すると、各桁につきkステップかかるため、kがlog n程度のとき、判定の計算量はO(k²)です。ここでは乗算は最大100回で、文字列にはk文字分のメモリが必要です。
アルゴリズム
nを10進数の文字列に変換し、その長さを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による整数除算でその桁を取り除けます。そのため、何も残らなくなるまで10で割るループで桁数を数えられます。9474 は 947、94、9、0 となり、4回のステップなので、k = 4 です。
数字は10種類しかないので、何かを加算する前に、0から9までの d についてテーブル powers[d] = d^k を作ります。すると各桁の処理は、k 回の乗算ではなく、1回の参照で済みます。判定は O(log n) 時間となり、テーブルのサイズは固定で10なので、必要な領域は O(1) です。
2つ目のループで再び桁を取り出し、合計に powers[m % 10] を加えます。各項はゼロまたは正なので、合計が減ることはなく、n を超えた時点で答えは false です。999999999 の場合、3桁目の処理後にそうなり、その値は 3 × 387420489 = 1162261467 です。n = 10^9 は10桁であり、9^10 = 3486784401 となるため、テーブルには依然として64ビットが必要です。
アルゴリズム
nのコピーを 0 になるまで 10 で割って桁数を数えます。この桁数をkとします。- 64 ビット整数で、0 から 9 までの各桁
dについてpowers[d] = d^kを設定します。 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は拒否します。また、7^3 = 343なので、1より大きい1桁の数はすべて拒否します。 - 合計が32ビットです。
999999999の各桁のべき乗の合計は3486784401で、表の項目9^10も同じ数です。Cではこのオーバーフローの動作は未定義です。JavaとC#では負の数に折り返され、Rustのデバッグビルドではパニックが発生します。long、long long、またはi64を使いましょう。 - 浮動小数点数によるべき乗。Cの
powとJavaのMath.powはdoubleを返します。Cの一部のランタイムでは、整数よりわずかに小さい値（たとえば5^2に対する24.999...）が返されることがあり、キャストすると24に切り捨てられます。代わりにループ内で整数同士を乗算しましょう。 - 誤った値との比較。各桁を処理するループでは
nを0まで割っていくため、コピーを使って処理し、合計を元の値と比較しましょう。 - 科学表記法。Rでは、
as.character(1e9)は"1e+09"となり、5文字です。そのため、文字列を使うRの解法ではsprintf("%.0f", n)で書式化します。
よくある質問4
アームストロング数とは何ですか？
アームストロング数（ナルシシスティック数とも呼ばれます）は、それぞれの桁を桁数乗した値の合計が、その数自身と等しくなる数です。153 は 1^3 + 5^3 + 3^3 = 153 となるため該当し、9474 は 9^4 + 4^4 + 7^4 + 4^4 = 9474 となるため該当します。1桁の数はすべて該当します。d^1 = d だからです。
アームストロング数はいくつありますか？
10進法では、正の数であるものはちょうど88個あり、最も大きいものは39桁です。k桁の数は少なくとも10^(k-1)である一方、その各桁のべき乗和は最大でもk × 9^kであり、61桁以上になると和が数に追いつくことはないため、リストは有限です。1から10^9までには31個あります。
アームストロング数の判定に64ビット整数が必要なのはなぜですか？
入力値は32ビットに収まりますが、各桁を累乗した値の合計は、数値の数倍になることがあります。999999999の場合、9 × 9^9 = 3486784401となり、2^31-1 = 2147483647を上回ります。ここでは32ビットの合計値はオーバーフローするため、合計値と累乗値には64ビット型を使いましょう。
アームストロング数を判定する時間計算量はどれくらいですか？
nの桁数はおよそlog nで、ここでは最大でも10桁です。各桁を取り出し、それぞれの累乗を10個の要素からなる表で調べる方法は、時間計算量がO(log n)、空間計算量がO(1)です。各桁についてループでd^kを再計算すると、時間計算量はO(log² n)になりますが、このサイズなら依然として高速です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isArmstrong(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 153
期待値
true