CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第93回「ナルシストなナルシシスト数」

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

• ナルシシスト数に関する問題。

(ウイキペディアより引用)

n桁の自然数であって、その各桁の数のn乗の和が、元の自然数に等しくなるような数をいう。例えば、 であるから、153 はナルシシスト数である。

十進法に限らず、他の基数においても同様にナルシシスト数を定義できる。

• 標準入力から nが与えられる。n進数で2桁以上のナルシシスト数を小さい方からn個求め、標準出力にn進数で順に出力する。
• nは10以下の整数。

方針

全探索()するより他に良い方法を思いつかなかった。
しかしながら、問題文より、答えを10個出力すれば打ち切れるので全探索をする事にした。

サンプルとして10進法の例が書かれてあり、10進法での10個目の答えは「93084」となっているので、（組み込み関数の内部処理を無視すれば）nの最大で約93,000回ほどのループ（x定数倍）で答えがでる。
その他の基数でのナルシシスト数の個数は不明で、10個に満たない場合、最悪のケースで=約3億8千万回ループする可能性があるが、それで時間制限に間に合わなかった場合は、改めて考え直す事にした。
実装してからローカルでテストすると、十分間に合ったのでそのまま提出した。
（提出結果はのケースで約0.3秒で正解）

なお、rubyでは

• 10進法の数値を任意のn進法の文字列に変換して表示するメソッド
• n進法の文字列を10進法の数値に変換するメソッド

をともに備えているので、これを利用し、n進法で2桁の最小値()からn桁の最大値()までの整数を都度n進法に変換し比較、ナルシシスト数と一致したものを出力した。
組み込み関数を用いればRubyでの実装は簡単であった。

実装(Ruby)

では、

Sponsored Link