C++で偶数・奇数の積を持つ順序対の個数を数える方法

正の整数からなる長さ n の配列が与えられたとき、arr[x] と arr[y] の積が偶数または奇数になる順序対 (arr[x], arr[y]) の個数を数えるのが本記事の目的です。なお、(arr[i], arr[j]) と (arr[j], arr[i]) は順序が異なるため、別々のペアとしてカウントします。

計算方法はシンプルです。2重の for ループで配列を走査して各ペアを取り出し、その積を計算します。積が偶数であれば偶数積ペアのカウントを、奇数であれば奇数積ペアのカウントを、それぞれ2ずつ増やします（(a, b) と (b, a) を別々に数えるため）。

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

入力例1

Arr[] = { 1, 1, 2, 3 }、N = 4

出力例1

偶数積ペアの個数：6　奇数積ペアの個数：6

説明： 積が奇数になる有効なペアは以下の通りです。

Arr[0] & Arr[1] → (1,1)、Arr[1] & Arr[0] → (1,1)　count=2
Arr[0] & Arr[3] → (1,3)、Arr[3] & Arr[0] → (3,1)　count=2
Arr[1] & Arr[3] → (1,3)、Arr[3] & Arr[1] → (3,1)　count=2　合計=6

積が偶数になる有効なペアは以下の通りです。

Arr[0] & Arr[2] → (1,2)、Arr[2] & Arr[0] → (2,1)　count=2
Arr[1] & Arr[2] → (1,2)、Arr[2] & Arr[1] → (2,1)　count=2
Arr[2] & Arr[3] → (2,3)、Arr[3] & Arr[2] → (3,2)　count=2　合計=6

入力例2

Arr[] = { 2, 2, 2 }、N = 3

出力例2

偶数積ペアの個数：6　奇数積ペアの個数：0

説明： すべての要素が偶数のため、積が奇数になるペアは存在しません。

Arr[0] & Arr[1] → (2,2)、Arr[1] & Arr[0] → (2,2)　count=2
Arr[1] & Arr[2] → (2,2)、Arr[2] & Arr[1] → (2,2)　count=2
Arr[0] & Arr[2] → (2,2)、Arr[2] & Arr[0] → (2,2)　count=2　合計=6

アルゴリズムの考え方

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

• 配列の長さを格納する変数 n を定義します。

• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、積が偶数・奇数それぞれになるペアの個数を出力します。

• 2重の for ループを使って、ペアを構成する各要素に対して配列を走査します。

• 外側のループは 0 ≤ i ＜ n−1、内側のループは i ＜ j ＜ n の範囲で回します。

• arr[i] * arr[j] % 2 == 0 が成り立てば積は偶数です。(a,b) と (b,a) を2つのペアとして数えるため、偶数積ペアのカウント count1 に2を加算します。

• 上記の条件が偽の場合は、奇数積ペアのカウント count2 に2を加算します。

• すべてのループが終了した時点で、count1 には積が偶数になるペアの総数、count2 には積が奇数になるペアの総数が格納されています。

• 最後に count1 と count2 を結果として出力します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
void countPairs(int arr[], int n){
    int count1=0; // 偶数積ペアの個数
    int count2=0; // 奇数積ペアの個数
    int prod=1;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            prod=arr[i]*arr[j];
            if(prod%2==0) // 積が偶数の場合
                { count1+=2; } //(a,b)と(b,a)を2つのペアとしてカウント
            else
                { count2+=2; }
        }
    }
    cout<<"Even Product pairs: "<<count1;
    cout<<endl<<"Odd Product pairs: "<<count2;
}
int main(){
    int arr[] = { 1,2,7,3 };
    int n = sizeof(arr) / sizeof(int);
    countPairs(arr, n);
    return 0;
}

実行結果

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

Even Product pairs: 6
Odd Product pairs: 6

このように、2重ループによる全ペアの走査と偶奇の判定だけで、O(n²) の計算量で偶数・奇数の積を持つ順序対の個数を簡単に求められます。