目次
解いた問題
学び
最初に考えた解法
正解
なぜ循環すると言い切れるのか
各桁の平方和はどんなに大きい数でも上限が決まっている
範囲が有限ならいつか同じ値に戻る
感想
解いた問題
leetcode 202. Happy Number
ある数値が与えられて、各桁の二乗の合計を取るという処理を繰り返していき、最終的に1になれば元となった数値をHappyNumberとしてTrueを返却、それ以外はFalseを返してねって問題。
学び
- アルゴリズムの元になっているのは数学である
- 2ポインタ法はかなり応用の幅が広い
- アルゴリズムの背景知識を理解するとアルゴリズムそのものも覚えやすくなる
最初に考えた解法
考えることとしては「どのように桁ごとに計算していくか」「どのように処理を終わらせるか」の2つに分解。
「どのように桁ごとに計算していくか」については、入力nに対して% 10を使用して余りを取り出し、その後// 10で下1桁を削るのを繰り返して全桁を取得する、という方法を考えた。
「どのように処理を終わらせるか」については、ハッピーナンバーは1と同値になるかを判定すればいいが、ループをどのように検出すればいいかわからなかった。
そもそも計算をしていった先に同じ値にたどり着くのか、それとも1にならない数字の組み合わせのようなものがあるのか...
なんとなく数学的な知識が必要だなと感じたので、実装はあきらめて答えを確認することにした。
「知らないと解けない系問題」だと考えたが果たして...
正解
下記が正解。
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(x: int) -> int:
total = 0
while x > 0:
digit = x % 10
total += digit * digit
x //= 10
return total
slow = n
fast = get_next(n)
# fast は 2ステップ、slow は 1ステップ進む
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
まさかの2ポインタ法の応用...
ウサギと亀の時みたいな slowと fastで進む速度をずらして確認する方法だった～～
ウサギと亀とは？という方は下記をご覧ください。
https://zenn.dev/zenn_mita/articles/fe0e6b6b79e18e
そうなると、前提として「ハッピーナンバー以外は必ずループが存在する」という前提の元動いていることになる。
なぜそうなるのか気になったので調べてみました。
なぜ循環すると言い切れるのか
結論としては、「各桁の平方和」は、ある一定の有限な範囲に必ず収束するため、同じ数が必ず再出現し、ループが発生するため、だそうです。
...なんで？？？
ある一定とは？なぜ収束すると言い切れる？という観点で疑問が残りますね。
上記が説明できればなんとなく同じ数が出現することは理解できるので、もう少し調べてみます。
各桁の平方和はどんなに大きい数でも上限が決まっている
入力のnが何桁であろうと、1桁1桁が「0~9」の範囲で収まるため、有限桁の数字が入力であればそれらの桁の二乗和も有限であるという結論が導かれる。
また、最大数を考えるとすべての数字が9であるとき最大となるので、上限もわかる。
例えば10桁の数字が nに入ってくるとすると、1桁あたりの値は$9^2 = 81$となり、それが10桁あるので、$81 * 10 = 810$となる。
つまり、桁数ごとに上限が存在しているので、0からその上限までの個数のどれかの値を繰り返し計算するという処理になっている。
範囲が有限ならいつか同じ値に戻る
本処理においては同じ処理が繰り返されるため、先ほど述べたように有限個数の範囲から抜けることなく計算される。
つまり、それが繰り返されたところで結局はその有限個から抜け出せないということに繋がる。
そして計算が無限に続けられるという前提があれば、有限の状態を無限に変化させていくため、必ずどこかで同じ値が再出現すると言い切れる。
先の10桁の例でいくと0から810までの811個の状態があるが、812回のループを繰り返した時点で同じ値が出ることが確定している、ということになる。
これを数学的には鳩ノ巣原理というらしい。
そして、同じ数字が再出現した時点で同じ計算が走ることとなるため、確定で循環が生まれているといえるわけだ。
結論
この問題では必ず数値は循環する。その循環の仕方は2つある。
-
1を含むループ -
1を含まないループ
1を含むと1→1→1→...となり、循環しているといえるのだ。
感想
アルゴリズムを解いていたと思ったらいつの間にか数学の勉強になっていた...
これはこれで面白い。
引き続き継続していきます！