C++-এ অ্যারেতে রেঞ্জের গড় (Mean of Range in Array)

এই সমস্যাতে, n সংখ্যক পূর্ণসংখ্যার একটি অ্যারে এবং m সংখ্যক কোয়েরি দেওয়া থাকে। আমাদের কাজ হল প্রতিটি কোয়েরিতে দেওয়া রেঞ্জের গড় (mean) এর পূর্ণসংখ্যা মান (round down) বের করা।

উদাহরণ

ইনপুট:

array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]

আউটপুট:

7 9

সমাধানের পদ্ধতি

দুটি পদ্ধতিতে সমাধান করা যায়:

সরাসরি পদ্ধতি: প্রতিটি কোয়েরির জন্য লুপ চালিয়ে রেঞ্জের সব উপাদান যোগ করে গড় বের করা। এটি সহজ কিন্তু বড় অ্যারেতে দ্রুত নয়।
প্রিফিক্স সম (Prefix Sum) পদ্ধতি: একটি প্রিফিক্স সম অ্যারে তৈরি করা যেখানে prefixSum[i] = ০ থেকে i ইনডেক্স পর্যন্ত সব উপাদানের যোগফল। তারপর প্রতিটি কোয়েরির জন্য O(1) সময়ে গড় বের করা যায়।

প্রিফিক্স সম ব্যবহার করে সমাধান

ফর্মুলা:

Mean = (prefixSum[upper] - prefixSum[lower-1]) / (upper - lower + 1)

যদি lower = 0 হয়, তবে prefixSum[lower-1] = 0 ধরা হয়।

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
#define MAX 100
using namespace std;

int prefixSum[MAX];

void initialisePrefixSum(int arr[], int n) {
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}

int queryMean(int l, int r) {
    int mean;
    if (l == 0)
        mean = (prefixSum[r] / (r + 1));
    else
        mean = ((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
    return mean;
}

int main() {
    int arr[] = {5, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    initialisePrefixSum(arr, n);
    cout << "Mean in 1st query: " << queryMean(1, 4) << endl;
    cout << "Mean in 2nd query: " << queryMean(2, 4) << endl;
    return 0;
}

আউটপুট

Mean in 1st query: 8
Mean in 2nd query: 9