見た数を集合に覚え、桁の 2 乗の和を繰り返して 1 に着くかを確かめる

正の整数を「各桁の 2 乗の和」に置き換える操作を繰り返し、いつか 1 に着くかを判定します。同じ数にもう一度来たら輪に入ったと分かるので、見た数を集合に覚えて止める練習です。

海外で定番の問題リスト 4 本には入っていません

問題

数遊びのゲームで、正の整数 n を「各桁を 2 乗して足した数」に置き換える操作を繰り返します。たとえば 28 は 2² + 8² = 68 になります。この操作を繰り返して、いつか 1 に着くなら真、いつまでも 1 に着かないなら偽を返す関数を書いてください。

1 に着いたら、そこで止めて真とします (1 を置き換えても 1 のままです)
n は 1 以上 2147483647 以下です

入力と出力の例

例 1

28 は 68、100、1 と進み、1 に着きます。

n = 28

true

例 2

11 は 2、4、16、37、58、89、145、42、20 と進み、また 4 に戻ります。4 から先は同じ並びを回り続け、1 には着きません。

n = 11

false

例 3

7 は 49、97、130、10、1 と進みます。1 桁の数でも、1 に着くものがあります。

n = 7

true

面接での聞かれ方

面接では、最初の 1 問として短く出されることが多い問題です。

「この操作を繰り返して 1 になるかを返してください」
書き始めると「1 にならないとき、いつ止めますか？」と聞かれます
書き終えたあとに「集合を使わずに、記憶 O(1) で書けますか？」と続くことがあります

芯は、1 に着かない数は同じ数の輪を回り続けると気づくことです。「同じ数にもう一度来たら止める」と言えれば、あとは素直に書けます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは 1 回分の操作を関数にします。n % 10 でいちばん下の桁を取り出して 2 乗を足し、n を 10 で割った商に置き換える、を n が 0 になるまで繰り返します。

段 2

次の数は今の数だけで決まるので、同じ数にもう一度来たら、その先はまったく同じ並びを繰り返します。そこで 1 に着いていなければ、この先も着きません。また、10 桁の数でも次の数は 9² × 10 = 810 以下なので、数がどこまでも大きくなることはなく、いつかは必ず同じ数に戻ります。

段 3

見た数を集合に覚えながら進みます。1 に着いたら真、集合にもうある数に来たら偽を返します。

解答

Python

def next_num(n):
    total = 0
    while n > 0:
        d = n % 10
        total += d * d
        n //= 10
    return total


def is_happy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False
        seen.add(n)
        n = next_num(n)
    return True

JavaScript

function nextNum(n) {
  let total = 0;
  while (n > 0) {
    const d = n % 10;
    total += d * d;
    n = Math.floor(n / 10);
  }
  return total;
}

function isHappy(n) {
  const seen = new Set();
  while (n !== 1) {
    if (seen.has(n)) {
      return false;
    }
    seen.add(n);
    n = nextNum(n);
  }
  return true;
}

Go

func nextNum(n int) int {
	total := 0
	for n > 0 {
		d := n % 10
		total += d * d
		n /= 10
	}
	return total
}

func isHappy(n int) bool {
	seen := map[int]bool{}
	for n != 1 {
		if seen[n] {
			return false
		}
		seen[n] = true
		n = nextNum(n)
	}
	return true
}

JavaScript の / は小数まで割るので、Math.floor で切り捨てます。

計算量

1 回の置き換えは、桁の数だけの手間で O(log n) です
2 回目からの数はどれも 810 以下なので、繰り返しの回数は 810 回ほどで頭打ちになります。全体の時間は O(log n) と見てかまいません
使う記憶は、集合に入る数の分です。これも 810 個ほどで頭打ちです
集合の代わりに、1 歩ずつ進む数と 2 歩ずつ進む数を追いかける書き方 (遅いのと速いのが輪の中で出会う) にすると、記憶は O(1) になります

よくある間違い

止める条件を書かない。 1 に着くまで回すだけだと、例 2 のような数でいつまでも終わりません
回数で打ち切る。「100 回で着かなければ偽」のように決め打ちすると、なぜその回数で足りるのかを説明できません。同じ数に戻ったかで止めます
桁の 2 乗を n % 10 ** 2 と書く。 Python では ** が先に計算されるので、n % 100 になってしまいます。桁を d に取り出してから d * d を足します
JavaScript で n / 10 をそのまま使う。 商が小数になり、桁を取り出す繰り返しが正しく終わりません

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def is_happy(n: int) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(is_happy(28))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します