ইনপুট হিসাবে একটি অ্যারে 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 ].
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
নিষ্পাপ দৃষ্টিভঙ্গি
আমরা দুটি পদ্ধতি ব্যবহার করে এই সমস্যার সমাধান করব। নিষ্পাপ পদ্ধতিতে, লুপগুলির জন্য দুটি ব্যবহার করে এবং i এবং j সূচকগুলির মধ্যে প্রতিটি সাবয়েরের জন্য উপাদানগুলির গুণফল k দ্বারা বিভাজ্য কিনা তা পরীক্ষা করে দেখুন৷ যদি হ্যাঁ তাহলে ইনক্রিমেন্ট কাউন্ট।
-
ইনপুট হিসাবে একটি পূর্ণসংখ্যা অ্যারে অ্যারে [] এবং k নিন।
-
ফাংশন product_k(int arr[], int size, int k) একটি অ্যারে এবং k নেয় এবং সাব-অ্যারেগুলির হিসাব প্রদান করে যার গুণফল k দ্বারা বিভাজ্য৷
-
ইনপুট হিসাবে প্রাথমিক গণনা নিন।
-
ট্রাভার্স arr i=0 থেকে i
-
প্রতিটি সাবয়ারের arr[ i থেকে j ] এর জন্য, arr[k] কে temp-এ গুণ করুন।
-
যদি পণ্যের তাপমাত্রা k দ্বারা বিভাজ্য হয় তবে বৃদ্ধির সংখ্যা।
-
তিনটি লুপের শেষে, ফলাফল হিসাবে গণনা করুন।
দক্ষ পদ্ধতি
এই পদ্ধতিতে প্রতিটি সাবয়ারে অতিক্রম করার পরিবর্তে, আমরা সেগমেন্ট ট্রিতে পণ্যগুলি সংরক্ষণ করব। এখন k দ্বারা বিভাজ্য এই গাছ থেকে পণ্য ব্যবহার করুন. এবং সেই অনুযায়ী সংখ্যা বৃদ্ধি করুন।
-
ইনপুট হিসাবে একটি পূর্ণসংখ্যা অ্যারে অ্যারে [] এবং 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) শুরু এবং শেষের মধ্যে সাবয়ারের গুণফল খুঁজে পেতে ব্যবহৃত হয়৷
-
যদি প্রথম>শেষ বা প্রথম>শেষ বা শেষ <শুরু রিটার্ন 1।
-
যদি প্রথম>=শেষ এবং শেষ<=শেষ তাহলে arr_2[fir]%k.
ফেরত দিন -
লেভেল=প্রথম+শেষ>> 1 সেট করুন (2 দিয়ে ভাগ করুন)।
-
এখন লেভেল এবং লেভেল+1 এর জন্য রিকার্সিভ কল চেক() এবং সেট_1 এবং সেট_2 এ স্টোর করুন।
-
গণনা=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
