C++でn番目の醜い数（Ugly Number）を効率的に求めるアルゴリズム

醜い数（Ugly Number）とは？

「醜い数」とは、素因数が2、3、5のみで構成される正の整数のことです。例えば、最初のいくつかの醜い数を並べると「1, 2, 3, 4, 5, 6, 8, 9, 10, 12…」となります。このとき、10番目の醜い数は12です。

本記事では、n番目の醜い数を動的計画法（DP）を使って効率的に求めるC++の実装方法を解説します。

アルゴリズムの考え方

醜い数は必ず「それより小さい醜い数」に2、3、または5を掛けた値になります。この性質を利用し、3つのポインタで候補値を管理しながら小さい順に配列へ格納していくのがポイントです。

手順は以下の通りです。

• サイズ n+1 の配列 v を用意する

• n = 1 の場合は 1 を返す

• 初期値として two := 2、three := 3、five := 5 を設定し、それぞれに対応するインデックス twoIndex、threeIndex、fiveIndex を 2 で初期化する

• i が 2 から n までの範囲で以下を繰り返す

  • curr := two、three、five の最小値とする

  • v[i] := curr を代入する

  • curr = two ならば、two := v[twoIndex] × 2 として twoIndex を1増やす

  • curr = three ならば、three := v[threeIndex] × 3 として threeIndex を1増やす

  • curr = five ならば、five := v[fiveIndex] × 5 として fiveIndex を1増やす

• 最後に v[n] を返す

最小値が一致した候補だけを更新することで、重複する値（例：6 = 2×3 = 3×2）が配列に複数回登録されるのを防げます。

C++での実装例

以下に実際の実装コードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int nthUglyNumber(int n) {
        vector <int> v(n + 1);
        if(n == 1){
            return 1;
        }
        int two = 2, three = 3, five = 5;
        int twoIdx = 2;
        int threeIdx = 2;
        int fiveIdx = 2;
        for(int i = 2; i <= n; i++){
            int curr = min({two, three, five});
            v[i] = curr;
            if(curr == two){
                two = v[twoIdx] * 2;
                twoIdx++;
            }
            if(curr == three){
                three = v[threeIdx] * 3;
                threeIdx++;
            }
            if(curr == five){
                five = v[fiveIdx] * 5;
                fiveIdx++;
            }
        }
        return v[n];
    }
};
main(){
    Solution ob;
    cout << (ob.nthUglyNumber(10));
}

実行結果

入力：

10

出力：

12

計算量について

この手法の時間計算量は O(n)、空間計算量も O(n) です。単純に各整数を1から順に素因数分解して判定する方法（O(n log n) 程度かそれ以上）と比べ、非常に高速にn番目の醜い数を求められる点が大きな利点です。