C++で同じ偶数要素と奇数要素を持つサブ配列をカウントします

正の整数の配列が与えられます。目標は、各サブ配列に同じ数の偶数要素と奇数要素が含まれるように、配列内の数値のサブ配列を見つけることです。配列が{1,2,3,4}の場合。その場合、サブ配列は{1,2}、{2,3}、{3,4}、{1,2,3,4}になります。そのようなサブアレイの数は4です。

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

入力 − arr [] ={1,3,5,7,8,3,2};

出力 −同じ偶数要素と奇数要素を持つサブアレイの数は− 4

説明 −サブアレイは− {7,8}、{8,3} {3,2}、{7,8,3,2}

入力 − arr [] ={2,4,6};

出力 −同じ偶数要素と奇数要素を持つサブアレイの数は− 0

説明 −すべての要素が偶数です。

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

このアプローチでは、配列要素間の差として可変温度（最初は0）を使用し、arr [i]が奇数の場合は1ずつインクリメントし、arr[i]が偶数の場合は1ずつデクリメントします。 tempの値が繰り返される場合、これらのインデックス間に同じ数の偶数と奇数のサブ配列が存在する必要があります。温度は正にも負にもなります。 2つのハッシュ配列arr_1[size+ 1]を正の差の頻度に、arr_2 [size+1]を負の差の頻度に使用します。

差temp<0ごとに、arr_1[-temp]からカウントする頻度を追加します。 [-（-temp）]は正のインデックスを与えます。

温度>0の差ごとに、arr_2[temp]からカウントする頻度を追加します。同じ差の値のすべてのオカレンスはサブアレイの一部になるため。これらの周波数を1ずつ更新します。

Arr[] = { 1,3,5,7,8,3,2 }

0から始まる温度値-

1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4.

サブアレイは− {7,8}、{8,3} {3,2}、{7,8,3,2}

• 初期配列をarr[]として取得します。

• 関数Sub_even_odd（int arr []、int size）は、配列とその長さを取得し、同じ偶数要素と奇数要素を持つサブ配列の数を返します。

• 初期カウントを0とし、変数tempを変数とします。変数は、奇数の値が検出されると増加し、偶数の値が検出されると減少します。

• 2つの配列arr_1[]とarr_2[]を使用して、温度の頻度を格納します。配列全体が偶数の場合、最大サイズ+1になる可能性のあるtempの正の値の場合はarr_1[]。

  配列全体が偶数の場合、最大サイズ+1になる可能性のあるtempの負の値の場合はarr_2[]。

• forループを使用してarr[]をトラバースします。

• arr [i]＆1 ==1の場合、これはarr[i]が奇数であることを意味します。温度を上げるそれ以外の場合は、温度を下げます。

• temp <0の場合、対応する頻度をarr_2[]から追加してカウントします。その頻度を1増やします。

• temp> 0の場合、対応する頻度をarr_1[]から追加してカウントします。その頻度を1増やします。

• 最終的に、同じ数の偶数要素と奇数要素を持つarr[]のサブ配列の数としてカウントしました

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

例

#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
   int count = 0;
   int temp = 0;
   int arr_1[size + 1] = {0};
   int arr_2[size + 1] = {0};
   arr_1[0] = 1;
   for (int i = 0; i < size; i++){
      if(arr[i] & 1 == 1)
         { temp++; }
      else
         { temp--; }
      if (temp < 0){
         count += arr_2[-temp];
         arr_2[-temp]++;
      }
      else{
         count += arr_1[temp];
         arr_1[temp]++;
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
   return 0;
}

出力

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

Count of subarrays with same even and odd elements are: 4