C++で1と0の数が等しいサブ配列をカウントします

0と1のみを含む配列arr[]が与えられます。目標は、0と1の出現がすべて等しくなるように、arr[]のすべてのサブ配列をカウントすることです。配列が[1,0,0]の場合、サブ配列は[1,0]のみになります。

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

入力 − arr [] ={0、0、1、1、1、0};

出力 − 1と0の数が等しいサブ配列の数は− 4

説明 − Subaaraysは−

arr[0 to 3] = [0,0,1,1],
arr[1 to 2] = [0,1],
arr[4 to 5] =[1,0],
Arr[0 to 5] =[0,0,1,1,1,0].

入力 − arr [] ={0、1、1、1、1};

出力 − 1と0の数が等しいサブ配列の数は− 1

説明 −サブアレイは次のようになります− arr [0 to 1] =[0,1]

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

2つのforループを使用して配列をトラバースし、可能なすべてのサブ配列を生成します。 i=0からi<=size-1およびj=iからj<=size-1まで。形成されるサブアレイは、arr[i]からarr[j]の間にあります。各サブアレイで0と1の頻度を数えます。等しい場合は、カウントを増やします。

• 数字の配列arr[]を取ります。

• 関数sub_zeroes_ones（int arr []、int size）は配列を受け取り、noが等しいサブ配列の数を返します。 0と1の。

• 初期カウントを0とします。

• i=0からi<=size-1およびj=0からj<=size-1までの2つのforループを使用して配列をトラバースします。

• サブ配列arr[i]からarr[j]の0と1の数について、2つの変数total_0、total_1を0とします。

• arr [j]を0および1と比較します。arr[j]が0または1の場合、それぞれのカウントをインクリメントします（total_0またはtotal_1）。

• total_0==total_1の場合。インクリメントカウント。 （サブアレイには、要素と同じ数の0と1があります）。

• 両方のループの終わりに、結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int sub_zeroes_ones(int arr[], int size){
   int count = 0;
   for (int i = 0; i <= size - 1; i++){
      int total_0 = 0;
      int total_1 = 0;
      for (int j = i; j <= size - 1; j++){
         if (arr[j] == 0){
            total_0++;
         }
         else if (arr[j] == 1){
            total_1++;
         }
         if(total_0 == total_1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {0, 1, 1, 0, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of subarrays with equal number of 1’s and 0’s are: "<<sub_zeroes_ones(arr, size);
}

出力

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

Count of subarrays with equal number of 1’s and 0’s are: 4