C++で指定された条件を満たす配列内の有効なペアをカウントする方法

N個の要素からなる配列 arr[] が与えられたとき、指定された条件を満たすすべての有効なペア (Arr[i], Arr[j]) の個数を求めることがゴールです。

有効なペアの条件

• Arr[i] == Arr[j](2つの要素の値が等しい)
• Arr[i] + Arr[j] の和が偶数である
• i + j < 120 を満たす
• さらに i != j(同一インデックス同士の組み合わせは不可)

注意: (Arr[i], Arr[j]) と (Arr[j], Arr[i]) は同じペアとして1回だけカウントします。

それでは、具体例を使って理解を深めましょう。

入力例1

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

出力

有効なペアの数: 2

説明

有効なペアは以下の2組です。

Arr[0] と Arr[4] → (3,3): 値が等しく、3+3=6 は偶数、i≠j、i+j=4<120
Arr[1] と Arr[3] → (2,2): 値が等しく、2+2=4 は偶数、i≠j、i+j=4<120

入力例2

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

出力

有効なペアの数: 0

説明

要素に重複が存在しないため、i != j となる (a, a) 型のペアは1つも作れません。

プログラムで使用しているアプローチ

• ランダムな整数で初期化した整数型配列 Arr[] を用意します。
• 配列 Arr[] の長さを格納する変数 n を定義します。
• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、条件を満たす有効なペアの数を返します。
• ペアを構成する2つの要素それぞれについて、二重のforループで配列を走査します。
• 外側のループは 0<=i<n-1、内側のループは i<j<n の範囲で実行します。
• arr[i] と arr[j] の和を sum = arr[i] + arr[j] として計算します。
• sum % 2 == 0(和が偶数)かつ i + j < 120 であるかどうかを判定します。
• さらに arr[i] == arr[j] であれば有効なペアなので、カウントを1増やします。
• すべてのループが終了した時点で、count には有効なペアの総数が格納されています。
• count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[], int n){
    int count=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++) //j=i+1 なので i!=j のチェックは不要
        {
            int sum=arr[i]+arr[j];
            //有効なペアは i != j
            if( sum%2==0 && i+j<120){
                if( arr[i]==arr[j] ) //有効なペア
                {
                    count++;
                    cout<<endl<<" a:"<<arr[i]<<"b: "<<arr[j];
                }
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {1,2,3,2,4,1,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout <<endl<<"Valid pairs in array:"<<countPairs(arr, n);
    return 0;
}

出力

Valid pairs in array:
a:1 b: 1
a:2 b: 2
a:4 b: 4
3

この実行結果では、(1,1)、(2,2)、(4,4) の3組が有効なペアとして検出されています。最後に出力されている「3」が countPairs 関数の戻り値、つまり配列内の有効なペアの総数です。