C++-এ সর্বোচ্চ এলিমেন্ট k-এর চেয়ে বড় সাব-অ্যারে সংখ্যা গণনা

আমাদের একটি ইন্টিজার অ্যারে arr[] এবং একটি ভেরিয়েবল k দেওয়া আছে। লক্ষ্য হল এমন সাব-অ্যারে বের করা যাদের সর্বোচ্চ (maximum) এলিমেন্ট k-এর চেয়ে বড়।

উদাহরণ

ইনপুট: arr[] = {1,2,5,3}, k=3

আউটপুট: ৬

ব্যাখ্যা: ৫ থাকা সাব-অ্যারেগুলো: [5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]।

ইনপুট: arr[] = {1,2,3,4,5}, k=4

আউটপুট: ৫

অ্যালগরিদম

মোট সাব-অ্যারে = n*(n+1)/2। আমরা k-এর চেয়ে ছোট বা সমান এলিমেন্ট বিশিষ্ট সাব-অ্যারে বাদ দিব। কন্টিগুয়াস সেগমেন্ট যেগুলো শুধু k-এর চেয়ে ছোট এলিমেন্ট দিয়ে গঠিত, তাদের লেন্থ l হলে সেগুলো থেকে l*(l+1)/2 সাব-অ্যারে বने। এগুলো বাদ দিয়ে বাকি গুলোই কাঙ্ক্ষিত।

1. অ্যারে, আকার এবং k ইনপুট নিন।
2. count = 0।
3. while লুপে অ্যারে ট্রাভার্স করুন।
4. যদি arr[i] > k হয়, স্কিপ করুন।
5. অন্যথায় ইনার while দিয়ে arr[i] <= k থাকা পর্যন্ত লেন্থ temp গণনা করুন।
6. count += temp*(temp+1)/2।
7. শেষে: count = total_subarrays - count।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

int maximum_k(int arr[], int size, int k) {
    int count = 0;
    int i = 0;
    while (i < size) {
        if (arr[i] > k) {
            i++;
            continue;
        }
        int temp = 0;
        while (i < size && arr[i] <= k) {
            i++;
            temp++;
        }
        count += temp * (temp + 1) / 2;
    }
    count = (size * (size + 1) / 2) - count;
    return count;
}

int main() {
    int arr[] = {4, 1, 2, 7, 8, 3};
    int k = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays whose maximum element is greater than k are: " 
         << maximum_k(arr, size, k);
    return 0;
}

আউটপুট

Count of subarrays whose maximum element is greater than k are: 14