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

正の整数からなる長さnの配列が与えられます。この問題の目標は、arr[x]とarr[y]の和が偶数になるペア、および奇数になるペアのそれぞれについて、順序対(arr[x], arr[y])の個数を数えることです。なお、(arr[i], arr[j])と(arr[j], arr[i])は異なるペアとして数えます。

解法では、2つのforループを使って配列を走査し、各ペアについて和を計算します。和が偶数であれば偶数和のカウントを2増やし、奇数であれば奇数和のカウントを2増やします。

それでは、具体的な例で確認しましょう。

例1

入力: Arr[]= { 1,1,2,3 }、N=4
出力: 偶数和のペア数 − 6、奇数和のペア数 − 6

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

Arr[0] & Arr[2] → (1,2)、Arr[2] & Arr[0] → (2,1) … カウント=2
Arr[1] & Arr[2] → (1,2)、Arr[2] & Arr[1] → (2,1) … カウント=2
Arr[2] & Arr[3] → (2,3)、Arr[3] & Arr[2] → (3,2) … カウント=2
合計 = 6

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

Arr[0] & Arr[1] → (1,1)、Arr[1] & Arr[0] → (1,1) … カウント=2
Arr[0] & Arr[3] → (1,3)、Arr[3] & Arr[0] → (3,1) … カウント=2
Arr[1] & Arr[3] → (1,3)、Arr[3] & Arr[1] → (3,1) … カウント=2
合計 = 6

例2

入力: Arr[]= { 2,2,2 }、N=3
出力: 偶数和のペア数 − 6、奇数和のペア数 − 0

説明: 和が偶数になる有効なペアは以下の通りです。

Arr[0] & Arr[1] → (2,2)、Arr[1] & Arr[0] → (2,2) … カウント=2
Arr[0] & Arr[2] → (2,2)、Arr[2] & Arr[0] → (2,2) … カウント=2
Arr[1] & Arr[2] → (2,2)、Arr[2] & Arr[1] → (2,2) … カウント=2
合計 = 6
すべての要素が偶数のため、和が奇数になるペアは存在しません。

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

• ランダムな整数で初期化された整数型配列arr[]を用意します。
• 配列Arr[]の長さを格納する変数nを定義します。
• 関数countPairs(int arr[], int n)は、配列とその長さを引数として受け取り、和が偶数になるペアと奇数になるペアの個数を出力します。
• ペアを構成する各要素に対して、2つのforループで配列を走査します。
• 外側のループは0≦i＜n−1、内側のループはi＜j＜nの範囲で繰り返します。
• (arr[i]+arr[j])%2==0 が成り立つかどうかを判定します。真の場合、(arr[i],arr[j])と(arr[j],arr[i])を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 sum=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            sum=arr[i]+arr[j];
            if(sum%2==0) // 和が偶数の場合
                { count1+=2; } // (a,b)と(b,a)を別々のペアとして数える
            else
                { count2+=2; }
        }
    }
    cout<<"Even Sum pairs: "<<count1;
    cout<<endl<<"Odd Sum pairs: "<<count2;
}
int main(){
    int arr[] = { 1,2,3,2 };
    int n = sizeof(arr) / sizeof(int);
    countPairs(arr, n);
    return 0;
}

出力

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

Even Sum pairs: 4
Odd Sum pairs: 8

補足：O(n)で求める効率的な方法

二重ループを用いる上記の方法の計算量はO(n²)ですが、偶数と奇数の要素数を数えるだけでO(n)で答えを求めることもできます。配列中の偶数の個数をE、奇数の個数をOとすると、偶数同士または奇数同士の和は必ず偶数、偶数と奇数の和は必ず奇数になるという性質から、偶数和の順序対の数は「E×(E−1)＋O×(O−1)」、奇数和の順序対の数は「2×E×O」で計算できます。大きな配列を扱う場合には、こちらの方法が効果的です。