簡単 0件解決済み 正答率0%

ハッピー数

各桁の 2 乗の和を求める操作を繰り返したとき、1 にたどり着くかどうかを判定します。

このチャレンジで学べること

  • 各桁の 2 乗の和を計算する
  • 集合や 2 つのポインタで数列の繰り返しを検出する
  • 2 つの条件のどちらかでループを止める

問題

原文(英語)を表示

正の整数から始めて、その数を各桁の 2 乗の和で置き換えます。これを繰り返していき、いつか 1 になれば、最初の数はハッピー数です。そうでなければ、この操作は 1 を含まないループに入り、その数はハッピー数ではありません。たとえば 7 → 49 → 97 → 130 → 10 → 1 となるので、7 はハッピー数です。

happy_number(n) を実装してください。

ハッピー数でない場合にもループを止められるよう、数列が繰り返しに入ったことに気づく仕組みが必要です。

入力

n: 最初の数。

出力

1 にたどり着けば true、そうでなければ false を返してください。1 自身もハッピー数です。

制約

1 ≤ n ≤ 10^9

例

例 1
入力:
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。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。