【C++】ソート済み配列から等比数列を形成するトリプルをすべて見つける方法

問題概要

重複のない正の整数からなるソート済み配列が与えられます。この中から、整数の公比をもつ等比数列(幾何級数)を形成するすべてのトリプル(3つ組)を見つけましょう。たとえば、配列が [1, 2, 6, 10, 18, 54] の場合、求めるトリプルは (2, 6, 18) と (6, 18, 54) であり、どちらも公比 3 の等比数列になっています。

解き方の考え方

この問題は、配列の2番目の要素から順に各要素を「中央の要素」として固定し、それより左(小さい側)と右(大きい側)の要素を探索することで解けます。中央の要素 arr[j] が等比数列の真ん中になるためには、左右の要素 arr[i]、arr[k] との間に次の関係が成り立つ必要があります。

arr[j] / arr[i] = arr[k] / arr[j] = r(公比)

言い換えれば、「arr[i] × arr[k] = arr[j]²」が成立すれば、(arr[i], arr[j], arr[k]) は等比数列を形成していることになります。両端のポインタ i と k を、比率の大小関係に応じて状況ごとに動かしながら条件を調べていくのがポイントです。

アルゴリズムの流れ

• 配列の2番目の要素(インデックス1)から後ろから2番目の要素までを、順に中央要素 j として扱います。
• i を j−1、k を j+1 として初期化します。
• arr[j] / arr[i] と arr[k] / arr[j] が一致すればトリプルとして出力します。
• 比率が一致しない場合は、小さい方の比率の側へポインタを移動させて調整します。

C++による実装例

#include<iostream>
using namespace std;
void getTriplets(int arr[], int n) {
   for (int j = 1; j < n - 1; j++) {
      int i = j - 1, k = j + 1;
      while (i >= 0 && k <= n - 1) {
         while (arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) {
            cout << "("<< arr[i] << ", " << arr[j] << ", " << arr[k] << ")" << endl;
               k++;
               i--;
         }
         if(arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) {
            if(arr[j] / arr[i] < arr[k] / arr[j])
               i--;
         else
            k++;
         }else if (arr[j] % arr[i] == 0)
            k++;
         else
            i--;
      }
   }
}
int main() {
   int arr[] = {1, 2, 6, 10, 18, 54};
   int n = sizeof(arr) / sizeof(arr[0]);
   getTriplets(arr, n);
}

実行結果

(2, 6, 18)
(6, 18, 54)

計算量について

各中央要素 j ごとに、ポインタ i と k が互いに近づきながら一度だけ走査を行うため、全体の時間計算量は O(n²) です。また、追加の記憶領域がほとんど不要で、空間計算量は O(1) で済みます。全組み合わせを総当たりするナイーブな三重ループ(O(n³))に比べ、効率よくすべてのトリプルを列挙できるのがこの手法の利点です。