C++で積が指定された数と等しくなるトリプレットの個数を数える方法

整数のみで構成される長さ n の整数型配列 Arr[] と、ある数 M が与えられます。この問題の目的は、要素の積が M と等しくなる Arr[] の三つ組（トリプレット）の個数を数えることです。

これには 3 重の for ループを使用します。arr[x] * arr[y] * arr[z] == M かつ x ≠ y ≠ z を満たす組み合わせが見つかるたびに、カウントを増やしていきます（0 ≦ x, y, z ＜ n）。

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

入力

arr[]= { 1,2,3,0,2,4 }, M=24

出力

積が M となるトリプレットの数: 2

説明

arr[x] * arr[y] * arr[z] == M となるトリプレットは以下の通りです。
Arr{} = [ 1,2,3,0,2,4 ] → (2,3,4) : 2×3×4 = 24
Arr{} = [ 1,2,3,0,2,4 ] → (3,2,4) : 3×2×4 = 24
※ 配列には 2 が 2 つ含まれているため、(2,3,4) の組み合わせが 2 通り成立します。
トリプレットの合計数: 2

入力

arr[]= {2,2,2,2,2}, M=6

出力

積が M となるトリプレットの数: 0

説明

すべてのトリプレットの積は 8 になるため、条件を満たす組み合わせは存在しません。
トリプレットの合計数: 0

プログラムで使用しているアプローチ

• ランダムな整数で初期化された整数型配列 Arr[] を用意します。

• 変数 N に配列 Arr[] の長さを格納します。

• 関数 productisM(int arr[], int n, int m) は、配列とその長さを受け取り、積が m に等しくなるトリプレットの個数を返します。

• トリプレットの個数を数えるための変数 count を 0 で初期化します。

• トリプレットを構成する各要素について、3 重の for ループで配列を走査します。

• 最も外側のループは 0 ≦ i ＜ n-2、内側のループは i ＜ j ＜ n-1、最も内側のループは j ＜ k ＜ n の範囲で繰り返します。

• arr[i] * arr[j] * arr[k] == m であるかを判定し、真であれば count をインクリメントします。

• すべてのループが終了した時点で、count には条件を満たすトリプレットの総数が格納されています。

• 結果として count を返します。

例

#include <bits/stdc++.h>
using namespace std;
int productisM(int arr[], int n, int m){
    int count = 0;
    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++){
                int prod = arr[i]*arr[j]*arr[k];
                if(prod==m)
                    { count++; }
            }
        }
    }
    return count;
}
int main(){
    int Arr[]={ 1,2,3,0,2,4 };
    int N=6; // 配列の長さ
    int M=24;
    cout <<endl<< "積がMとなるトリプレットの数 : "<<productisM(Arr,N,M);
    return 0;
}

出力

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

積がMとなるトリプレットの数: 2