原案: admin

まず、操作を \(1\) 度かけた際に整数 \(n\) が何に変化するかを求める関数 \(f(n)\) を実装しましょう。
整数 \(n\) を桁ごとに分解する方法はいくつかあります。

• \(n\) を \(10\) で割った余りを見た後 \(n\) を \(10\) で割る(小数点以下切り捨て) ことを、 \(n\) が \(0\) になるまで繰り返す
• \(n\) を文字列として解釈させ、各桁を抽出する

ここで、 \(f(n)\) が実装できたとしましょう。

以下のどちらの方針を取っても、この問題に正解できます。

• \(n\) を \(f(n)\) に置き換えることを繰り返す。 \(1\) に到達したら答えは Yes であり、そうでない時に同じ数に戻ってきた場合は答えは No であると判定する。
• \(n\) を \(f(n)\) に置き換えることを十分な回数 ( 例えば \(1000\) 回 ) 繰り返した結果が \(1\) かどうかで判定する

証明は少し難しいので、先に実装例を示します。 \(2\) つの方針のうち前者の実装を以下に示します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int f(int n){
  string s=to_string(n);
  int res=0;
  for(auto &nx : s){
    res+=(nx-'0')*(nx-'0');
  }
  return res;
}

int main(){
  int n;
  cin >> n;
  set<int> history;
  while(n>1){
    if(history.find(n)!=history.end()){
      cout << "No\n";
      return 0;
    }
    history.insert(n);
    n=f(n);
  }
  cout << "Yes\n";
  return 0;
}

余談: 実は、ハッピー数は Wikipedia に記事があるほど 有名な概念で、実装例をインターネット上から探して活用することも可能です。

解説中の解法の正当性を示します。

制約より \(1 \le N \le 2026\) なので、与えられる \(N\) は \(4\) 桁以下です。
このとき、 \(f(N) \le 9^2+9^2+9^2+9^2 = 324\) であり、 \(f(N)\) が \(3\) 桁以下であることが分かります。
\(f(N)\) が \(3\) 桁以下なので、置き換えを \(2\) 度行った \(f(f(N)) \le 9^2+9^2+9^2 = 243\) ということも言えます。
さらに、 \(243\) 以下の整数 \(y\) に対して同じ理由から \(f(y) \le 243\) 、つまり \(243\) 以下の整数に置き換えを掛けても \(243\) 以下にしかならないことが言えます。
また、置き換えを繰り返すことで \(1\) に辿り着くことなく以前通った整数に戻ってきた場合、そのループを繰り返して永遠に \(1\) に辿り着くことがないことも分かります。
そして、 \(243\) 以下の整数 \(y\) に一度辿り着くと、 \(243\) 以下の整数にしか置き換えられないということから、 \(y\) から置き換えを \(243\) 回行うと必ず一度通った整数に戻っていることが分かります。
もし一度でも \(1\) に辿り着いていれば \(f(1)=1\) なので \(1\) から動けなくなるはずであり、逆に置き換えを十分な回数繰り返してなお \(1\) に辿り着いていないのであれば \(1\) を含まないループに陥っていることが分かります。
それに必要な反復回数は高々 \(300\) 回程度であることが分かり、適切な実装の下でこの問題に誤答もしくは実行制限時間超過することなく正解できることが示せます。