問題
正の整数から始めて、その数を各桁の 2 乗の和で置き換えます。これを繰り返していき、いつか 1 になれば、最初の数はハッピー数です。そうでなければ、この操作は 1 を含まないループに入り、その数はハッピー数ではありません。たとえば 7 → 49 → 97 → 130 → 10 → 1 となるので、7 はハッピー数です。
happy_number(n) を実装してください。
ハッピー数でない場合にもループを止められるよう、数列が繰り返しに入ったことに気づく仕組みが必要です。
入力
n: 最初の数。
出力
1 にたどり着けば true、そうでなければ false を返してください。1 自身もハッピー数です。
制約
1 ≤ n ≤ 10^9
例
入力:
n = 19
期待される出力:
expected = True
入力:
long long n = 19;
期待される出力:
bool expected = true;
入力:
long n = 19;
期待される出力:
bool expected = true;
解説
1² + 9² = 82、8² + 2² = 68、6² + 8² = 100、1² + 0² + 0² = 1 となるので、19 はハッピー数です:true。
入力:
n = 4
期待される出力:
expected = False
入力:
long long n = 4;
期待される出力:
bool expected = false;
入力:
long n = 4;
期待される出力:
bool expected = false;
解説
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 と、1 にたどり着かないまま繰り返すので、答えは false です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
数を、その各桁の 2 乗の和に変換する補助関数を書きましょう。
ヒント 2
ハッピー数でない数は、一度出てきた値をまた出します。これまでに出てきた値を覚えておきましょう。
ヒント 3
数列はすぐに数百未満まで小さくなるので、集合は大きくなりません。
目安の計算量
1 つの数につき O(log n) ステップ、2 つのポインタを使えば追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。