C++で配列内に積が存在するペアの個数を数える方法

問題概要

整数型の要素からなる配列が与えられたとき、配列から2つの要素を選んでペアを作り、その積を計算します。そして、その積が元の配列の中にも存在するかどうかを調べ、条件を満たすペアの個数を求めるのがこの記事の目的です。

入力 − int arr[] = {6, 2, 3, 1, 5, 10}

出力 − 積が同じ配列内に存在するペアの個数：7

説明 − 与えられた配列から作れるペアは次の15通りです。(6, 2), (6, 3), (6, 1), (6, 5), (6, 10), (2, 3), (2, 1), (2, 5), (2, 10), (3, 1), (3, 5), (3, 10), (1, 5), (1, 10), (5, 10)。このうち、積が同じ配列内に存在するのは (2, 3)→6、(6, 1)→6、(3, 1)→3、(2, 5)→10、(1, 5)→5、(2, 1)→2、(1, 10)→10 の7ペアです。

入力 − int arr[] = {2, 4, 8, 5, 10}

出力 − 積が同じ配列内に存在するペアの個数：2

説明 − 作れるペアは (2, 4), (2, 8), (2, 5), (2, 10), (4, 8), (4, 5), (4, 10), (8, 5), (8, 10), (5, 10) の10通りです。このうち積が配列内に存在するのは (2, 4)→8、(2, 5)→10 の2ペアです。

素朴なアプローチ（全探索）の手順

まずは最もシンプルな全探索による解き方を見てみましょう。すべてのペアについて積を計算し、その積が配列内に存在するかどうかを線形探索で確認します。

• 整数型の配列を受け取り、そのサイズを計算して関数に渡します。
• 条件を満たすペアの個数を格納する一時変数 count を宣言します。
• i を 0 から配列サイズ未満までループさせます。
• その内側で j を i + 1 から配列サイズ未満までループさせます。
• product = arr[i] * arr[j] としてペアの積を計算します。
• さらに k を 0 から配列サイズ未満までループさせます。
• k のループ内で product == arr[k] であれば count を1増やします。
• 最後に count を返し、結果を出力します。

効率的なアプローチ（STL set を活用）

線形探索の代わりに STL の set を使うと、要素の存在確認を高速に行えます。set は内部で平衡二分木（赤黒木）を使用しており、挿入・検索が O(log n) で実行できるのが特徴です。

• 整数型の配列を受け取り、そのサイズを計算して関数に渡します。
• 条件を満たすペアの個数を格納する一時変数 count を宣言します。
• int 型の STL set である pro を作成します。
• i を 0 から配列サイズ未満までループさせ、arr[i] を set の pro に挿入します。
• 続いて i を 0 から、j を i + 1 からそれぞれ配列サイズ未満まで二重ループさせます。
• product = arr[i] * arr[j] として積を計算します。
• pro.find(product) != pro.end() であれば count を1増やします。
• 最後に count を返し、結果を出力します。

コード例（素朴なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size){
    int product = 1;
    int count = 0;
    for(int i = 0 ; i<size ; i++){
        for(int j = i+1;j<size;j++){
            product = arr[i] * arr[j];
            for(int pro = 0 ; pro < size; pro++){
                if(product == arr[pro]){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 2, 3, 1, 5, 10};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size);
    return 0;
}

出力

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

Count of pairs whose products exist in same array are: 7

コード例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size){
    set< int > pro;
    int count = 0;
    int product = 1;
    for (int i = 0 ; i < size; i++){
        pro.insert(arr[i]);
    }
    for (int i = 0 ; i < size; i++){
        for (int j = i + 1; j < size ; j++){
            product = arr[i] * arr[j];
            if(pro.find(product) != pro.end()){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 2, 3, 1, 5, 10};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size);
    return 0;
}

出力

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

Count of pairs whose products exist in same array are: 7

計算量の比較

• 素朴なアプローチ：三重ループを使用するため時間計算量は O(n³)。追加の記憶領域が不要なため空間計算量は O(1) です。
• 効率的なアプローチ：set への挿入・検索が O(log n)、ペアの組み合わせが O(n²) であるため、時間計算量は O(n² log n)、空間計算量は O(n) です。

まとめ

この記事では、配列内のペアの積が同じ配列内に存在する場合のペア数を数える方法を紹介しました。小規模なデータであれば全探索でも十分ですが、set を活用することで存在確認の処理を高速化でき、より大きな入力サイズにも対応しやすくなります。