นับอาร์เรย์ย่อยที่ผลิตภัณฑ์หารด้วย k ลงตัวใน C++

กำหนดอาร์เรย์ arr[] และจำนวนเต็ม k เป็นอินพุต เป้าหมายคือการหาจำนวน subarray ของ arr[] เพื่อให้ผลคูณของ subarray นั้นหารด้วย 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 ].

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

แนวทางที่ไร้เดียงสา

เราจะแก้ปัญหานี้โดยใช้สองวิธี ในแนวทางที่ไร้เดียงสา เพียงสำรวจอาร์เรย์โดยใช้สองลูปและสำหรับแต่ละอาร์เรย์ย่อยระหว่างดัชนี i และ j ตรวจสอบว่าผลคูณขององค์ประกอบหารด้วย k ลงตัวหรือไม่ ถ้าใช่ก็นับเพิ่ม

• ใช้อาร์เรย์จำนวนเต็ม arr[] และ k เป็นอินพุต

• ฟังก์ชัน product_k(int arr[], int size, int k) รับอาร์เรย์และ k และคืนค่าจำนวนอาร์เรย์ย่อยที่ผลคูณหารด้วย k ลงตัว

• นับเริ่มต้นเป็นอินพุต

• ข้าม arr จาก i=0 ถึง i

• สำหรับแต่ละ subarray arr[ i ถึง j ] ให้คูณ arr[k] กับ temp.

• หากอุณหภูมิของผลิตภัณฑ์หารด้วย k ลงตัว ให้นับเพิ่ม

• เมื่อสิ้นสุดทั้งสามลูป ให้นับเป็นผลลัพธ์

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้แทนที่จะสำรวจแต่ละ subarray เราจะจัดเก็บผลิตภัณฑ์ในแผนผังกลุ่ม ตอนนี้ใช้ผลิตภัณฑ์จากต้นไม้นี้ที่หารด้วย k ลงตัว และเพิ่มขึ้นนับตามนั้น

• ใช้อาร์เรย์จำนวนเต็ม arr[] และ k เป็นอินพุต

• เราจะใช้แผนผังกลุ่มเป็นอาร์เรย์ arr_2[4 * size_2]

• ฟังก์ชัน set_in(int fit, int first, int last, const int* arr, int k) ใช้เพื่อสร้างแผนผังกลุ่มสำหรับผลิตภัณฑ์

• การตรวจสอบฟังก์ชัน (int fit, int first, int last, int start, int end, int k) ใช้เพื่อค้นหาผลคูณของ subarray ระหว่างจุดเริ่มต้นและจุดสิ้นสุด

• ถ้า first>สุดท้ายหรือ first>end หรือสุดท้าย

• ถ้า first>=last และ last <=end ให้คืนค่า arr_2[fir]%k.

• Set level=first+last>> 1 (หารด้วย 2 )

• ตอนนี้ตรวจสอบการโทรแบบเรียกซ้ำ () สำหรับระดับและระดับ +1 และเก็บไว้ใน set_1 และ set_2

• ตั้งค่า count=set_1+set_2 และนับคืน

• ฟังก์ชัน 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