C++で2つの配列から合計が偶数になるペアを数える方法

この記事では、整数型の要素を持つ2つの配列 arr_1[] と arr_2[] が与えられたとき、arr_1[] から1つの要素、arr_2[] からもう1つの要素を選んでペアを作り、そのペアの合計を計算して、合計が偶数になるペアの数を数える方法を解説します。

入力例と出力例

入力

int arr_1[] = {2, 3, 7, 1, 4}
int arr_2[] = {2, 4, 1, 3}

出力

Count Pairs from two arrays with even sum are: 10

説明

両方の配列から作成できるすべてのペアとその合計は次のとおりです。

(2, 2) = 4(有効)、(2, 4) = 6(有効)、(2, 1) = 3(無効)、(2, 3) = 5(無効)
(3, 2) = 5(無効)、(3, 4) = 7(無効)、(3, 1) = 4(有効)、(3, 3) = 6(有効)
(7, 2) = 9(無効)、(7, 4) = 11(無効)、(7, 1) = 8(有効)、(7, 3) = 10(有効)
(1, 2) = 3(無効)、(1, 4) = 5(無効)、(1, 1) = 2(有効)、(1, 3) = 4(有効)
(4, 2) = 6(有効)、(4, 4) = 8(有効)、(4, 1) = 5(無効)、(4, 3) = 7(無効)

このうち、合計が偶数になる有効なペアは10個あります。

入力

int arr_1[] = {3, 1, 2}
int arr_2[] = {2, 4}

出力

Count Pairs from two arrays with even sum are: 2

説明

作成できるペアは次のとおりです。

(3, 2) = 5(無効)、(3, 4) = 7(無効)、(1, 2) = 3(無効)
(1, 4) = 5(無効)、(2, 2) = 4(有効)、(2, 4) = 6(有効)

合計が偶数になる有効なペアは2個あります。

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

• 整数型の要素を持つ2つの配列を入力し、両方の配列のサイズを計算して、以降の処理のためにデータを関数に渡します。
• 合計が偶数になるペアの数を格納するための一時変数 count を用意します。
• i を 0 から配列1のサイズまで for ループで繰り返します。
• そのループの内側で、j を 0 から配列2のサイズまで別の for ループを開始します。
• arr_1[i] と arr_2[j] の合計を整数変数(ここでは sum)に格納します。
• sum % 2 == 0 かどうか、つまり sum が偶数かどうかを判定します。偶数であれば count を1増やします。
• count を返します。
• 結果を出力します。

例

#include <iostream>
using namespace std;
int even_pair(int arr_1[], int size_arr1, int arr_2[], int size_arr2){
    int count = 0;
    int odd = 0;
    for(int i = 0 ;i <size_arr1 ; i++){
        for(int j = 0; j<size_arr2 ; j++){
            int even = arr_1[i] + arr_2[j];
            if(even % 2 == 0){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr_1[] = {2, 3, 7, 1, 4};
    int arr_2[] = {2, 4, 1, 3};
    int size_arr1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr2 = sizeof(arr_2) / sizeof(arr_2[0]);
    cout<<"Count Pairs from two arrays with even sum are: "<<even_pair(arr_1, size_arr1, arr_2, size_arr2);
    return 0;
}

出力

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

Count Pairs from two arrays with even sum are: 10

より効率的なアプローチ(O(n + m))

すべてのペアを実際に足し合わせて調べなくても、数学的な性質を利用すれば効率よく答えを求められます。「偶数 + 偶数 = 偶数」「奇数 + 奇数 = 偶数」という性質があるため、答えは次の式で計算できます。

偶数ペアの数 = (arr_1 の偶数の個数 × arr_2 の偶数の個数) + (arr_1 の奇数の個数 × arr_2 の奇数の個数)

この方法では、各配列の偶数と奇数の個数を一度数えるだけでよいため、時間計算量は二重ループの O(n × m) から O(n + m) に改善され、配列が大きい場合に大きな差が生まれます。

このように、C++では単純な二重ループによる全探索と、偶数・奇数の個数を利用した最適化のどちらの方法でも、合計が偶数になるペアの数を簡単に求めることができます。