【C++】積が指定した値に等しいトリプレットの個数を数える方法（重複を許可）

整数型の配列 Arr[] が与えられます。この記事の目的は、3つの要素の積が指定された数 p に等しいトリプレット（3つ組）の個数を数えることです。値が同一のトリプレットでも、使用する要素が異なれば別々にカウントします。

例えば、配列 [1,2,3,1,2] における (1,2,3) と (3,1,2) は値の並びこそ同じですが、参照している要素が異なるため、別個のトリプレットとして扱います。

具体的な例で確認しましょう。

入出力例

例1

入力 − arr[]= { 1,2,3,2,4,1,5 }, p=4

出力 − トリプレットの個数: 3

説明 −

Triplet 1 [ 1,2,3,2,4,1,5 ] → (1,2,2) 積=4
Triplet 2 [ 1,2,3,2,4,1,5 ] → (1,4,1) 積=4
Triplet 3 [ 1,2,3,2,4,1,5 ] → (2,2,1) 積=4
積が4となるトリプレットは合計3個です。

例2

入力 − arr[]= { 1,1,2,1,2,2 }, p=8

出力 − トリプレットの個数: 1

説明 −

Triplet 1 [ 1,1,2,1,2,2 ] → (2,2,2) 積=8
積が8となるトリプレットは合計1個です。

プログラムで使用するアプローチ

• ランダムな数値で初期化した整数配列 Arr[] を用意します。
• 目標となる積の値を格納する変数 product と、配列 Arr[] の長さを格納する変数 N を定義します。
• 関数 countTriplets(int arr[], int n, int p) は、配列・その長さ・積の値を引数として受け取り、積が p に等しいトリプレットの個数を返します。
• トリプレットの個数を数えるための変数 count を 0 で初期化します。
• 各トリプレットの積を計算する変数 prod を用意し、初期値は 1 とします。
• トリプレットを構成する3つの要素を選ぶために、三重の for ループで配列を走査します。
• 最も外側のループは 0≦i＜n-2、中間のループは i＜j＜n-1、最も内側のループは j＜k＜n の範囲で回します。
• prod = arr[i]*arr[j]*arr[k] を計算し、prod == p が成り立てば count をインクリメントします。
• すべてのループが完了した時点で、count には条件を満たすトリプレットの総数が格納されています。
• 最後に count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[],int n,int p){
    int count = 0;
    int prod=1;
    for (int i = 0; i < n-2; i++){
        for (int j = i+1; j < n-1; j++){
            for (int k = j+1; k < n; k++){
                prod=arr[i]*arr[j]*arr[k];
                if ( prod==p ){
                    count++;
                    // cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; //デバッグ用の出力
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr[]={ 1,2,3,6,1,6,3,2,1};
    int N=9; //配列の長さ
    int product=6;
    cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N,product);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Number of triplets : 18.

まとめ

このアプローチでは、三重ループによってすべての組み合わせを網羅的に調べるため、時間計算量は O(n³) となります。シンプルで理解しやすい方法ですが、配列サイズが大きくなると処理時間が増加します。ハッシュマップなどを使用すれば、より効率的に解くことも可能です。まずは本記事のような素直な実装でロジックを理解し、必要に応じて最適化を検討するとよいでしょう。