C++のバイナリ配列で0と1のみで構成されるサブ配列をカウントします

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

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

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

出力 − 0のみのサブアレイは：4 1のみのサブアレイは：6

説明 − Subaaraysは−

For all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] )
For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4],
arr[2-4] )

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

出力 − 0のみのサブアレイは：2 1のみのサブアレイは：2

説明 − Subaaraysは−

For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] )
For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )

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

0と1のみのサブ配列を個別にカウントするために、配列を2回トラバースします。 2つのカウンターcount_0とcount_1を取り、配列内の連続する0と1のカウントを格納します。そのようなカウントごとに、可能なサブ配列はcount_0 *（count_0 + 1）/ 2であり、count_1についても同様です。

配列の最後に到達するまで、これをtotal_0カウントに追加します。 1についても同様のプロセスを実行します。

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

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

• サブアレイの初期カウントをtemp_0およびtemp_1とします。

• 0と1の一時的な連続カウントをcount_0とcount_1として取ります。

• forループを使用してi=0からI

• 現在の要素が0インクリメントcount_0の場合。

• そうでない場合は、count_0の数が0のすべての可能なサブ配列をtemp_one_0 =count *（count + 1）/2として計算します。

• これを、これまでにすべて0が見つかったサブアレイの以前のtemp_0に追加します。

• count_1、temp_one_1、temp_1などの変数を使用してforループfor1を使用して同様のプロセスを実行します。

• 両方のトラバーサルの終了時に、temp_0とtemp_1には、すべて0とすべて1を持つarr内のすべてのサブ配列のそれぞれのカウントがあります。

例

#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
   int count_1 = 0;
   int count_0 = 0;
   int temp_1 = 0;
   int temp_0 = 0;
   for (int i = 0; i < size; i++){
      if (arr[i] == 1){
         count_1++;
      }
      else{
         int temp_one_1 = (count_1) * (count_1 + 1) / 2;
         temp_1 = temp_1 + temp_one_1;
         count_1 = 0;
      }
   }
   for (int i = 0; i < size; i++){
      if (arr[i] == 0)
         { count_0++; }
      else{
         int temp_one_0 = (count_0) * (count_0 + 1) / 2;
         temp_0 = temp_0 + temp_one_0;
         count_0 = 0;
      }
   }
   if (count_1){
      int temp_one_1 = (count_1) * (count_1 + 1) / 2;
      temp_1 = temp_1 + temp_one_1;
   }
   if (count_0){
      int temp_one_0 = (count_0) * (count_0 + 1) / 2;
      temp_0 = temp_0 + temp_one_0;
   }
   cout<<"Subarrays with only 0's are : "<<temp_0;
   cout<<"\nSubarrays with only 1's are : "<<temp_1;
}
int main(){
   int arr[] = { 0, 0, 0, 1, 1, 0, 1};
   int size = sizeof(arr) / sizeof(arr[0]);
   sub_zero_one(arr, size);
   return 0;
}

出力

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

Subarrays with only 0's are : 7
Subarrays with only 1's are : 4