Đếm các mảng con có tích chia hết cho k trong C ++

Cho một mảng arr [] và một số nguyên k làm đầu vào. Mục đích là tìm số mảng con của arr [] sao cho tích các phần tử của mảng con đó chia hết cho k.

Ví dụ

Đầu vào

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

Đầu ra

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

Giải thích

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

Đầu vào

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

Đầu ra

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

Giải thích

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Cách tiếp cận ngây thơ

Chúng tôi sẽ giải quyết vấn đề này bằng hai cách tiếp cận. Theo cách tiếp cận đơn giản, chỉ cần duyệt qua mảng bằng cách sử dụng hai vòng lặp for và đối với mỗi mảng con giữa các chỉ mục i và j, kiểm tra xem tích của các phần tử có chia hết cho k hay không. Nếu có thì tính gia tăng.

Lấy một mảng số nguyên arr [] và k làm đầu vào.
Hàm product_k (int arr [], int size, int k) nhận một mảng và k và trả về tổng số mảng con có tích chia hết cho k.
Lấy số lượng ban đầu làm đầu vào.
Traverse arr từ i =0 đến i
Đối với mỗi mảng con arr [i đến j], nhân arr [k] với temp.
Nếu nhiệt độ sản phẩm chia hết cho k thì tính tăng dần.
Khi kết thúc tất cả ba vòng lặp, trả về kết quả là số lượng.

Phương pháp tiếp cận hiệu quả

Trong cách tiếp cận này thay vì duyệt qua từng mảng con, chúng ta sẽ lưu trữ các sản phẩm trong cây phân đoạn. Bây giờ sử dụng các sản phẩm từ cây này chia hết cho k. Và tăng số lượng tương ứng.

Lấy một mảng số nguyên arr [] và k làm đầu vào.
Chúng tôi sẽ triển khai cây phân đoạn dưới dạng mảng arr_2 [4 * size_2].
Hàm set_in (int fit, int first, int last, const int * arr, int k) được sử dụng để xây dựng cây phân đoạn cho các sản phẩm.
Kiểm tra hàm (int fit, int first, int last, int start, int end, int k) được sử dụng để tìm sản phẩm của mảng con giữa start và end.
Nếu đầu tiên> cuối cùng hoặc đầu tiên> kết thúc hoặc cuối cùng
Nếu đầu tiên> =cuối cùng và cuối cùng <=kết thúc thì trả về arr_2 [linh sam]% k.
Đặt cấp độ =đầu tiên + cuối cùng>> 1 (chia cho 2).
Bây giờ, hãy kiểm tra cuộc gọi đệ quy () cho cấp và cấp + 1 và lưu trữ trong set_1 và set_2.
Đặt số lượng =set_1 + set_2 và số lượng trả về.
Hàm product_k (int arr [], int size, int k) nhận arr [] và k và trả về số mảng con có tích chia hết cho k.
Lấy số lượng ban đầu là 0.
Đặt số lượng ban đầu là 0.
Đảo ngược bằng cách sử dụng hai vòng lặp for từ i =0 đến i
Nếu nhiệt độ này là 0 thì số gia tăng.
Số lượt trả lại là kết quả cuối cùng.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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

Ví dụ (Phương pháp Tiếp cận Hiệu quả)

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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