Happy Number
正の整数 n から始め、各桁の平方の和で何度も置き換えます。たとえば、12 は 1² + 2² = 5 になります。この処理で 1 に到達した場合、n はハッピー数です。そうでない場合は、1 を含まない数を永久に循環します。n がハッピー数なら true を、そうでなければ false を返してください。
関数
- ninteger
- テストする正の整数
- 戻り値boolean
- 各桁の数字の平方和を繰り返した結果が1に達する場合はtrue、無限ループする場合はfalse
制約
1 ≤ n ≤ 231-1
例
- 入力
- n = 7
- 出力
- true
- 説明
- 7 は 49 になり、次に 4² + 9² = 97、次に 130、次に 10、そして 1 になります。この過程は
1に到達するので、7 はハッピー数です。
- 入力
- n = 2
- 出力
- false
- 説明
- 2 は 4、16、37、58、89、145、42、20 となり、その後再び 4 になります。そこから同じ 8 つの数が永遠に繰り返され、
1には決して到達しません。
- 入力
- n = 100
- 出力
- true
- 説明
- 1² + 0² + 0² = 1 なので、100 は1回のステップで
1に到達します。
提出時に隠しテスト+16件
発展問題
1 から 10^6 までのハッピー数を、すべての開始値について最初からたどるのではなく、1000 未満の数の答えを再利用して、どうすれば素早く数えられるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
いくつかの数から手作業で試してみましょう。7は5ステップで1に到達し、2は8ステップ後に4に戻ります。数が戻ってくることから、何がわかりますか？
各値はその直前の値だけに依存するため、ある数が繰り返された時点で、その後の並び全体も永遠に繰り返されます。問題は、すでに見た数に到達する前に、数列が1に到達するかどうかです。
訪れた数を集合に記録し、1に到達するか、同じ数が再び現れたら停止します。定数メモリで実行するには、
nから2つの探索者を進め、一方は1ラウンドに1ステップ、もう一方は2ステップ進めます。2つが出会うのはループの中だけです。
解説
この歩みが無限に続くことはありません。10桁の数は最大でも 10 × 81 = 810 に写り、1000未満の数は最大でも 3 × 81 = 243 に写るため、1ステップ後には1000未満の値の中にとどまり、必ず1に到達するか、数が繰り返されます。つまり、この問題はサイクル検出に帰着します。これまでに見た数を記録するか、遅い歩みと速い歩みを進めて、それらが出会うかどうかを確認します。
これまでに見たすべての数字を覚えておく
考え方
数列をたどり、出てきた各数をハッシュセットに保存します。次の数に進む前に、その数がすでにセットにあるか確認します。2の場合、セットには2、4、16、37、58、89、145、42、20が入り、次の値は4になります。これはすでにセットにあるため、1に到達せずに数列がループに入ったことがわかります。したがって、2はハッピー数ではありません。1に到達すると、trueで数列の探索が終了します。
これは、次の数が現在の数だけに依存するため正しい方法です。ある数が再び現れると、その後はすべて同じように繰り返されるため、新しい数は現れず、1に到達することもありません。
数列の探索は短時間で終わります。最初のステップではnのO(log n)桁を読み取り、その後の値はすべて1000未満です。この範囲では、1に到達するか数が繰り返されるまでに訪れる異なる数は最大20個です。セットにはそれらの数が格納されます。Cコードでは、1000個の要素を持つフラグ配列をセットとして使い、最初のステップの後、すべての値が1000未満になってから記録を始めます。
アルゴリズム
- 空のハッシュセット
seenを作成します。 nが 1 でない間、nがseenに含まれている場合はfalseを返します。- それ以外の場合は、
nをseenに追加し、nをその各桁の平方の合計に置き換えます。 - ループが終了すると、
nは 1 です。trueを返します。
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
seen = set()
while n != 1:
if n in seen:
return False # back at an earlier number: a loop without 1
seen.add(n)
n = digitSquareSum(n)
return True速い歩行者と遅い歩行者（Floydの循環検出）
考え方
各数を、1本の矢印がその桁の二乗和を指すノードと考えます。nから矢印をたどると、矢印が1自身を指す1に到達するか、ループに入ります。これはサイクルを含む可能性のある連結リストの形であり、Floydのアルゴリズムは何も保存せずにサイクルを検出します。slowは1ラウンドに1歩、fastは2歩進みます。
ループに1が含まれていなければ、両方の歩行者はループを回り続け、各ラウンドでfastはslowに対して1歩ずつ差を詰めるため、同じ数に立つまで間隔が1ずつ縮まります。2の場合、7ラウンド後に42で出会います。たどって1に到達する場合、fastが先にそこへ着き、そのまま留まります。1の桁の二乗和は1だからです。したがって、fastが1になるか、歩行者同士が出会うまで続け、fastが1かどうかを答えます。
7の場合、slowは7、49、97と進み、fastは49、130、1と進みます。そしてfastが1のところでループが止まります。ラウンド数は歩行の長さの小さな倍数以下なので、実行時間は集合を使う方法と同じで、メモリ使用量は整数2個分です。
アルゴリズム
- 数値の各桁の2乗の合計を返すヘルパー関数を作成します。
slow = nを設定し、fastにはnの1ステップ先の数値を設定します。fastが1ではなく、slowとfastが異なる間、slowを1ステップ、fastを2ステップ進めます。fastが1かどうかを返します。
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
slow = n
fast = digitSquareSum(n)
# fast moves two steps for every step of slow; they meet only inside a loop.
while fast != 1 and slow != fast:
slow = digitSquareSum(slow)
fast = digitSquareSum(digitSquareSum(fast))
return fast == 1
落とし穴と境界ケース
各桁の計算は短いものです。ほとんどの間違いは、ループをいつ止めるかに関するものです。
- ほかに終了条件を設けず、値が1になるまでループする。2の場合、このループは終わりません。
slowとfastを同じ数から始め、最初の移動の前にslow != fastを判定する。ループは一度も実行されず、7が不幸数と判定されます。fastを1ステップ先から始めるか、最初の比較の前に両方を移動させます。- Floyd版で
slow == 1を返す。fastが先に1に到達してループはすぐに停止しますが、slowはまだ97にいる可能性があります。 - 各桁の2乗ではなく各桁を合計する、または数全体を2乗する。12の場合、次の値は
1² + 2² = 5であり、3でも144でもありません。 - 歩行者が出会ったら常に
nを不幸数と判定する。1は自分自身に写るため、歩行者は1でも出会います。出会った場所を確認するか、fastが1になったらすぐに停止します。
よくある質問4
なぜプロセスは必ず1に到達するか、ループするのでしょうか？
d 桁の数は最大でも 81 × d に写るため、大きな数はすぐに小さくなります。2^31-1 以下の数は、1 回のステップで 1000 未満になり、1000 未満の数は最大でも 243 に写ります。この過程でたどる値は 1000 未満の範囲に閉じ込められるため、必ず同じ値を再び通り、その後は循環します。自分自身に写る数は 1 だけです。
ハッピーナンバーの時間計算量はどれくらいですか？
最初のステップでは、nのO(log n)桁を読み取ります。それ以降の値はすべて1000未満で、遷移は最大20個の数値の間で繰り返されるため、全体の時間計算量はO(log n)です。ハッシュセットを使う方法では訪問した数値を保存し、Floydの方法ではO(1)の空間を使用します。
なぜ不幸な数はすべて最終的に4になるのでしょうか？
1000未満のすべての数を調べると、1を避けるループはちょうど1つだけです。4, 16, 37, 58, 89, 145, 42, 20、そして4に戻ります。どの数から始めても1000未満に下がるため、1にならない数はすべてこのループに入ります。解法では4に達した時点で終了できますが、面接ではその根拠を説明する必要があります。集合とフロイドの方法には、そのような知識は必要ありません。
ハッピーナンバーは連結リストのサイクルとどのように関係していますか？
どちらも、各項目から矢印を1つたどっていくと、すでに訪れた項目に戻ることがあるかを尋ねています。Happy Numberでは矢印は各桁の平方和で、連結リストでは次のポインターです。そのため、Floydの速いポインターと遅いポインターを使えば、どちらも一定のメモリ量で解けます。
Python
def isHappy(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 7
期待値
true