সাবঅ্রে যার গুণফল k দিয়ে বিভাজ্য C++-এ

একটি অ্যারে arr[] এবং একটি ইন্টিজার k ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো arr[]-এর সেই সাবঅ্রেগুলোর সংখ্যা বের করা যাদের এলিমেন্টগুলোর গুণফল k দিয়ে বিভাজ্য।

ইনপুট

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

আউটপুট

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

ব্যাখ্যা

সাবঅ্রেগুলো হবে: [ 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

ব্যাখ্যা

সাবঅ্রেগুলো হবে: [ 9 ], [ 9,7 ], [ 1,9 ], [ 1,9,7 ], [ 7,1,9 ], [ 7,1,9,7 ]।

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

সহজ পদ্ধতি (Naive Approach)

এই পদ্ধতিতে, সহজেই অ্যারের উপর দুটি ফর লুপ দিয়ে ট্রভারস করা হয় এবং প্রতিটি সাবঅ্রে জন্য ইন্ডেক্স i এবং j এর মধ্যে 엘িমেন্টগুলোর গুণফল k দিয়ে বিভাজ্য কিনা চেক করা হয়। হ্যাঁ হলে কাউন্ট বাড়ানো হয়।

• ইন্টিজার অ্যারে arr[] এবং k ইনপুট নেওয়া হয়।
• product_k(int arr[], int size, int k) ফাংশন অ্যারে এবং k নিয়ে কাউন্ট রিটার্ন করে।
• ইনিশিয়াল কাউন্ট ০।
• i=0 থেকে i<size এবং j=i থেকে j<size এবং k=i থেকে k<=j ট্রভারস।
• প্রতিটি সাবঅ্রে arr[i to j] এর জন্য arr[k] গুণ করে temp-এ রাখা হয়।
• temp % k == 0 হলে count++।
• তিনটি লুপ শেষে count রিটার্ন।

দক্ষ পদ্ধতি (Efficient Approach)

এই পদ্ধতিতে প্রতিটি সাবঅ্রে ট্রভারস না করে, সেগমেন্ট ট্রি-তে গুণফলগুলো স্টোর করা হয়। এখন এই ট্রি থেকে 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) ফাংশন start এবং end এর মধ্যে সাবঅ্রের গুণফল বের করে।
• শর্তমতো রিটার্ন ১ বা মডুলো k ভ্যালু।
• লেভেল ক্যালকুলেশন: level = (first + last) >> 1।
• রিকারসিভ কল check() লেভেল এবং লেভেল+১ এর জন্য এবং set_1, set_2-এ স্টোর।
• count = (set_1 * set_2) % k রিটার্ন।
• product_k(int arr[], int size, int k) ফাংশন কাউন্ট রিটার্ন করে।
• দুই ফর লুপে i=0 থেকে size, j=i থেকে size। temp = check(1, 0, size-1, i, j, k)।
• temp == 0 হলে count++।
• ফলাফল count রিটার্ন।

উদাহরণ (সহজ পদ্ধতি)

#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