【C++】2つの配列から剰余演算の結果がKになるペアを数える方法

問題の概要

正の整数からなる2つの配列と値 K が与えられます。目的は、(A, B) という形のペアのうち、A % B = K または B % A = K を満たすものを見つけることです。ここで A は最初の配列の要素、B は2番目の配列の要素に対応し、重複のない一意なペアの総数を求めます。

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

入力 − arr_1[] = {1,2,5,3,4}; arr_2[] = {7,1,3}; k=2

出力 − 剰余演算の結果が K となる2つの配列間のペアの数 − 2

説明 − 該当するペアは (5,7)、つまり (arr_1[2], arr_2[1]) で 7%5=2、および (5,3)、つまり (arr_1[2], arr_2[2]) で 5%3=2 の2つです。

入力 − arr_1[] = {2,5}; arr_2[] = {3,7}; k=1

出力 − 剰余演算の結果が K となる2つの配列間のペアの数 − 2

説明 − 該当するペアは (2,3)、つまり (arr_1[0], arr_2[0]) で 3%2=1、および (2,7)、つまり (arr_1[0], arr_2[1]) で 7%2=1 の2つです。

アルゴリズムの考え方

このアプローチでは、for ループを使って両方の配列を走査します。A % B = k または B % A = k（A は arr_1 の要素、B は arr_2 の要素）を満たすペアを、set<pair<int, int>> 型の変数 se に挿入していきます。set は同じ要素を自動的に1つしか保持しないため、最終的な se のサイズが「剰余演算の結果が k となる一意なペアの数」になります。

• 正の要素を持つ整数配列 arr_1[] と arr_2[]、およびそれぞれの長さ size_arr_1 と size_arr_2 を用意します。
• 整数 k を用意します。
• 関数 modulo_pairs(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int k) は、両方の配列とその長さを受け取り、要素同士の剰余演算の結果が k となるペアの数を返します。
• count の初期値を 0 とします。
• set<pair<int, int>> se; を宣言します。
• i = 0 から i < size_arr_1 まで arr_1[] を、j = 0 から j < size_arr_2 まで arr_2[] を二重ループで走査します。
• 各ペア (arr_1[i], arr_2[j]) に対して、まず arr_1[i] > arr_2[j] かどうかを判定します。真の場合は arr_1[i] % arr_2[j] == k を確認し、成立していればペア (arr_1[i], arr_2[j]) を set se に挿入します。
• そうでない場合は arr_2[j] % arr_1[i] == k を確認し、成立していればペア (arr_1[i], arr_2[j]) を set se に挿入します。
• count を se.size() として計算します。これにより一意なペアの総数が得られます。
• count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int modulo_pairs(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int k){
    int count = 0;
    set<pair<int, int>> se;
    for (int i = 0; i < size_arr_2; i++){
        for (int j = 0; j < size_arr_1; j++){
            if (arr_1[i] > arr_2[j]){
                if (arr_1[i] % arr_2[j] == k){
                    se.insert(make_pair(arr_1[i], arr_2[j]));
                }
            }
            else{
                if (arr_2[j] % arr_1[i] == k){
                    se.insert(make_pair(arr_2[j], arr_1[i]));
                }
            }
        }
    }
    count = se.size();
    return count;
}
int main(){
    int arr_1[] = { 2, 7, 1, 9 };
    int arr_2[] = { 4, 10, 3, 10 };
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int k = 3;
    cout<<"剰余演算の結果がKとなる2つの配列間のペアの数:"<<modulo_pairs(arr_1, arr_2, size_arr_1, size_arr_2, k);
    return 0;
}

実行結果

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

剰余演算の結果がKとなる2つの配列間のペアの数: 2

補足：計算量について

この手法はすべての要素の組み合わせを調べるため、時間計算量は O(N × M)（N、M はそれぞれの配列の長さ）となり、追加で必要な空間計算量は O(P)（P は条件を満たすペアの数）です。サンプルコードの場合、7%4=3 を満たすペア (7,4) と、10%7=3 を満たすペア (10,7) の2つが該当するため、結果は 2 になります。