C++の同じ配列に平均が存在するペアをカウントします

配列の各要素が[-1000,1000]の範囲になるように、整数の配列が与えられます。目標は、平均がその配列にも存在するように、配列の要素のペアを見つけることです。配列がarr[]=[1,2,3,4]の場合。その場合、ペアは（1,3）と（2,4）になります。これは、1,3の平均が2で、2,4の平均が3であり、2と3の両方が配列に存在するためです。カウントは2になります。

例を挙げて理解しましょう。

入力 − arr [] ={-1,2,5、-3,8,10}

出力 −同じ配列に平均が存在するペアの数は− 2

説明 −平均がarr []に存在するようなペアは次のとおりです。−（-1,5）avgは2、（2,8）avgは5です。Count=2

入力 − arr [] ={1,3,2,5,10,6}

出力 −同じ配列に平均が存在するペアの数は− 3

説明 −平均がarr []に存在するペアは次のとおりです。−（1,3）avgは2、（1,5）avgは3、（2,10）avgは6です。Count=3。

以下のプログラムで使用されているアプローチは次のとおりです

まず、配列のすべての要素に対して周波数配列を作成します。周波数配列のサイズは、負の要素も存在する可能性があるため、元の配列の2倍のサイズです。

負の数の頻度はインデックス0からインデックス1000までです。正の数の頻度はインデックス1000から2000までです。

ゼロ以外の周波数ごとにこれを実行します-

1. （freq [i]）*（freq [i] -1）/ 2を加算してカウントします。これは、2つの同じ数値の平均が数値そのものであるためです。配列に52がある場合。その場合、ペアの合計は（5 *（5-1））/ 2=10になります。

2. 上記のfreq[i]がゼロ以外の場合、連続する数値の平均は浮動小数点であり、配列には存在しないため、代替周波数のトラバースを開始します。

3. ゼロ以外のfreq[j]が見つかり、freq [（i + j）/2]もゼロ以外の場合。次に、freq [i] * freq [j]をカウントに追加します（各数値は他のすべての数値とペアになる可能性があるため）。

• 整数配列を取りますarr[]

• 関数average_pair（arr、size）は、配列とそのサイズを取得し、ペアの要素の平均が配列arr[]にも存在するようにペアの数を返します。

• 初期カウントを0とし、N=1000を初期化します。

• 周波数配列の長さをsize_2=2 * N + 1として計算します（範囲[-1000〜1000]

  の場合）

• 周波数配列を最初は0で初期化します。

• 負の要素の頻度が0から1000になり、その後正の要素になるように頻度配列を設定します。このために、インデックスにNを追加します。

• 各要素について、arr[i]は頻度配列をarr_freq[arr [i] + N] ++;

  として更新します。

• 次に、周波数配列をi=0からi

• ゼロ以外の周波数ごとに、（freq [i]）*（freq [i] -1）/ 2を追加して、条件1に従ってカウントします。

• arr_freq [i]がゼロ以外であるため、すべての代替周波数をトラバースします。

• temp_2をarr_freq[（i + j）/2]として計算します。

• ここで、temp_2がゼロ以外で、arr_freq [j]がゼロ以外の場合、条件3が満たされます。製品でカウントを更新します（arr_freq [i] * arr_freq [j]）;

• すべての反復が終了すると、カウントにはそのようなペアの総数が含まれます。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int average_pair(int arr[], int size_1){
   int count = 0;
   int N = 1000;
   int size_2 = (2 * N) + 1;
   int arr_freq[size_2] = { 0 };
   for (int i = 0; i < size_1; i++){
      int temp = arr[i];
      arr_freq[temp + N]++;
   }
   for (int i = 0; i < size_2; i++){
      if (arr_freq[i] > 0){
         int check = (arr_freq[i]) * (arr_freq[i] - 1);
         count += check / 2;
         for (int j = i + 2; j < 2001; j += 2){
            int temp_2 = arr_freq[(i + j) / 2];
            if (arr_freq[j] > 0 && temp_2 > 0){
               count += (arr_freq[i] * arr_freq[j]);
            }
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 2, 3, 1, 8, 9, 10 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of pairs with average present in the same array are: "<<average_pair(arr, size);
   return 0;
}

出力

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

Count of pairs with average present in the same array are: 2