C++でX以下の要素を持つサブ配列をカウントします

整数と変数Xを含む配列arr[]が与えられます。目標は、各サブ配列にX以下の要素のみが含まれるようにarr []のすべてのサブ配列をカウントすることです。たとえば、配列が[1、 2,3]およびX=2の場合、サブ配列は[1]、[2]、および[1,2]

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

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

出力 − X以下の要素を持つサブ配列の数は− 6

説明 − Subaaraysは−

[3], [2], [1], [3,2], [2,1], [3,2,1]

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

出力 − X以下の要素を持つサブ配列の数は− 4

説明 − Subaaraysは−

[3], [2], [1], [5]

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

元の配列arr[]と同じサイズのバイナリ配列temp_arr[]を作成しています。このバイナリ配列は、対応するarr [i]がX以下の場合は1、それ以外の場合は0になります。ここでtemp_arr []をトラバースし、連続1（arr []のX未満の要素）をチェックします。そのような各サブアレイの長さをtempに格納します。長さtempの配列の場合。サブアレイの合計はtemp*（temp + 1）/2になります。これを合計数に追加し、temp_arr[]の終わりまで続けます。

• 配列arr[]と変数Xを取ります。

• 関数sub_X（int arr []、int size、int x）は、配列とxを受け取り、x以下の要素のみを含むサブ配列の数を返します。

• 一時変数tempと、カウントなどのサブ配列の最終合計を取得します。

• arr[]と同じ長さのバイナリ配列temp_arr[]を取ります。

• forループを使用して配列arr[]をi=0からi

• 各要素arr[i]<=xについて、temp_arr [i] =1、それ以外は0に設定します。

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

• 要素temp_arr[i]==1.の場合、現在のインデックスiからtemp_arr [temp_2]（temp_2 =i + 1; temp_2

• すべて1のサブ配列の数は、temp=temp_2-iになります。

• このサブ配列にはすべて1があります。これは、arr[i]のすべての要素が<=xであることを意味します。サブ配列の合計は、temp_3 =temp *（temp + 1）/2になります。

• 両方のトラバーサルの終了時に、カウントには、x以下の数を持つarr内のすべてのサブアレイのカウントの総数が含まれます。

例

#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
   int count = 0, temp = 0;
   int temp_arr[size];
   for (int i = 0; i < size; i++){
      if (arr[i] <= x){
         temp_arr[i] = 1;
      }
      else{
         temp_arr[i] = 0;
      }
   }
   for (int i = 0; i < size; i++){
      if (temp_arr[i] == 1){
         int temp_2;
         for(temp_2 = i + 1; temp_2 < size; temp_2++){
            if(temp_arr[temp_2] != 1){
               break;
            }
         }
         temp = temp_2 - i;
         int temp_3 = (temp) * (temp + 1)/2;
         count = count + temp_3;
         i = temp_2;
      }
   }
   return count;
}
int main(){
   int arr[] = { 2, 6, 1, 10, 5, 3 };
   int x = 4;
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub-arrays which have elements less than or equal to X are: "<<sub_X(arr, size, x);
   return 0;
}

出力

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

Count of sub-arrays which have elements less than or equal to X are: 3