C++で積が​​kで割り切れるサブ配列をカウントします

配列arr[]と整数kを入力として指定します。目標は、arr []のサブアレイの数を見つけて、そのサブアレイの要素の積がkで割り切れるようにすることです。

例

入力

arr[] = {2, 1, 5, 8} k=4

出力

Count of sub-arrays whose product is divisible by k are: 4

説明

The subarrays will be:
[ 8 ], [ 5,8 ], [ 1,5,8 ], [ 2,1,5,8 ].

入力

arr[] = {7,1,9,7} k=9

出力

Count of sub−arrays whose product is divisible by k are: 6

説明

The subarrays will be:
[ 9 ], [ 9,7 ], [ 1,9 ], [ 1,9,7 ], [ 7,1,9 ], [ 7,1,9,7 ].

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

ナイーブアプローチ

この問題は、2つのアプローチを使用して解決します。単純なアプローチでは、2つのforループを使用して配列をトラバースし、インデックスiとjの間の各サブ配列について、要素の積がkで割り切れるかどうかを確認します。はいの場合、カウントをインクリメントします。

• 整数配列arr[]とkを入力として受け取ります。

• 関数product_k（int arr []、int size、int k）は、配列とkを取り、積がkで割り切れるサブ配列の数を返します。

• 初期カウントを入力として受け取ります。

• arrをi=0からi

• サブアレイarr[iからj]ごとに、arr[k]をtempに乗算します。

• 製品の温度がkで割り切れる場合は、カウントをインクリメントします。

• 3つのループすべての最後に、結果としてカウントを返します。

効率的なアプローチ

Wこのアプローチでは、各サブアレイをトラバースする代わりに、製品をセグメントツリーに格納します。ここで、kで割り切れるこのツリーの製品を使用します。それに応じてカウントを増やします。

• 整数配列arr[]とkを入力として受け取ります。

• セグメントツリーを配列arr_2[4*size_2]として実装します。

• 関数set_in（int fit、int first、int last、const int * arr、int k）は、製品のセグメントツリーを構築するために使用されます。

• 関数check（int fit、int first、int last、int start、int end、int k）は、開始と終了の間のサブ配列の積を見つけるために使用されます。

• 最初>最後または最初>終了または最後の場合<開始リターン1。

• first>=lastおよびlast<=endの場合、arr_2 [fir]％kを返します。

• level =first + last>> 1（2で除算）を設定します。

• ここで、levelとlevel + 1のcheck（）を再帰的に呼び出し、set_1とset_2に格納します。

• count =set_1+set_2を設定してcountを返します。

• 関数product_k（int arr []、int size、int k）は、arr []とkを取り、積がkで割り切れるサブ配列の数を返します。

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

• 初期カウントを0に設定します。

• i=0からi

• この温度が0の場合、カウントをインクリメントします。

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

例

#include <bits/stdc++.h>
using namespace std;
int product_k(int arr[], int size, int k){
   int count = 0;
   for (int i = 0; i < size; i++){
      for (int j = i; j < size; j++){
         int temp = 1;
         for (int k = i; k <= j; k++){
            temp = temp * arr[k];
         }
         if(temp % k == 0){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 1, 5, 8, 10, 12 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);
   return 0;
}

出力

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

Count of sub−arrays whose product is divisible by k are: 18

例（効率的なアプローチ）

#include <bits/stdc++.h>
using namespace std;
#define size_2 100002
int arr_2[4 * size_2];
void set_in(int fit, int first, int last, const int* arr, int k){
   if (first == last){
      arr_2[fit] = (1LL * arr[first]) % k;
      return;
   }
   int level = (first + last) >> 1;
   set_in(2 * fit, first, level, arr, k);
   set_in(2 * fit + 1, level + 1, last, arr, k);
   arr_2[fit] = (arr_2[2 * fit] * arr_2[2 * fit + 1]) % k;
}
int check(int fit, int first, int last, int start, int end, int k){
   if(first > last){
      return 1;
   }
   if(first > end){
      return 1;
   }
   if(last < start){
      return 1;
   }
   if (first >= start){
      if(last <= end){
         return arr_2[fit] % k;
      }
   }
   int level = (first + last) >> 1;
   int set_1 = check(2 * fit, first, level, start, end, k);
   int set_2 = check(2 * fit + 1, level + 1, last, start, end, k);
   int count = (set_1 * set_2) % k;
   return count;
}
int product_k(int arr[], int size, int k){
   int count = 0;
   for (int i = 0; i < size; i++){
      for (int j = i; j < size; j++){
         int temp = check(1, 0, size − 1, i, j, k);
         if (temp == 0){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 1, 5, 8, 10, 12};
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   set_in(1, 0, size − 1, arr, k);
   cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);
   return 0;
}

出力

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

Count of sub−arrays whose product is divisible by k are: 18