C++で醜い数（アグリー・ナンバー）のみを含む部分配列の最大長を求める方法

問題の概要

N個の要素を持つ配列 arr[] が与えられます（0 ≤ arr[i] ≤ 1000）。この問題では、醜い数（アグリー・ナンバー）のみを含む部分配列（サブ配列）の最大長を求めることが求められます。

醜い数とは、素因数が 2、3、5 のみである数のことを指します。それ以外の素因数（7、11、13など）を含む数は醜い数とはみなされません。

例えば、醜い数の数列は次のようになります。

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

具体例

入力配列が {1, 2, 7, 9, 120, 810, 374} の場合、答えは 3 となります。

これは、醜い数のみから構成される最長の部分配列が {9, 120, 810} であり、その長さが3だからです。なお、7 と 374 は素因数に7を含むため、醜い数ではありません。

アルゴリズム

• unordered_set を用意し、1000以下のすべての醜い数を事前にセットへ挿入しておきます。
• current_max（現在の連続長）と max_so_far（これまでの最大長）の2つの変数を使って配列を走査します。
• 各要素について、その値がセット内に存在するかどうかを確認します。
• 醜い数が見つかった場合は current_max を1増やし、max_so_far と比較します。
• current_max > max_so_far であれば、max_so_far = current_max として更新します。
• 醜い数以外の要素が見つかるたびに、current_max = 0 にリセットします。

醜い数の生成には、動的計画法の考え方を用いた効率的な手法を採用しています。既知の醜い数に2、3、5を掛けた値の中で最小のものを順次選んでいくことで、重複なく小さい順に醜い数を列挙できます。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;

// n番目の醜い数を動的計画法で求める関数
unsigned getUglyNumbers(int n) {
   int ugly[n];
   int i2 = 0, i3 = 0, i5 = 0;
   int next_multiple_of_2 = 2;
   int next_multiple_of_3 = 3;
   int next_multiple_of_5 = 5;
   int next_ugly_no = 1;
   ugly[0] = 1;
   for (int i = 1; i < n; i++) {
      next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5));
      ugly[i] = next_ugly_no;
      if (next_ugly_no == next_multiple_of_2) {
         i2 = i2 + 1;
         next_multiple_of_2 = ugly[i2] * 2;
      }
      if (next_ugly_no == next_multiple_of_3) {
         i3 = i3 + 1;
         next_multiple_of_3 = ugly[i3] * 3;
      }
      if (next_ugly_no == next_multiple_of_5) {
         i5 = i5 + 1;
         next_multiple_of_5 = ugly[i5] * 5;
      }
   }
   return next_ugly_no;
}

// 醜い数のみを含む部分配列の最大長を求める関数
int maxUglySubarray(int arr[], int n) {
   unordered_set<int> s;
   int i = 1;
   // 1000以下の醜い数をすべてセットに登録
   while (1) {
      int next_ugly_number = getUglyNumbers(i);
      if (next_ugly_number > 1000)
         break;
      s.insert(next_ugly_number);
      i++;
   }
   int current_max = 0, max_so_far = 0;
   // 配列を線形走査しながら最大連続長を更新
   for (int i = 0; i < n; i++) {
      if (s.find(arr[i]) == s.end())
         current_max = 0;
      else {
         current_max++;
         max_so_far = max(current_max, max_so_far);
      }
   }
   return max_so_far;
}

int main() {
   int arr[] = {1, 2, 7, 9, 120, 810, 374};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum sub-array size of consecutive ugly numbers = " << maxUglySubarray(arr, n) << endl;
   return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum sub-array size of consecutive ugly numbers = 3

計算量について

このアルゴリズムの時間計算量は O(N) です。醜い数の事前生成は定数回（1000以下の醜い数は86個程度）で済み、本体の配列走査は各要素を1度だけ確認するため線形時間で完了します。空間計算量も O(N) と効率的です。