আমাদের একটি অ্যারে arr[] এবং একটি সংখ্যা K দেওয়া আছে। লক্ষ্য হলো এমন সাবঅ্যারে গুলোর সংখ্যা বের করা যাতে সাবঅ্যারের সব উপাদান K-এর চেয়ে বড়। উদাহরণস্বরূপ, অ্যারে [1,2,3] এবং K=1 হলে সাবঅ্যারে: [2], [3], [2,3]।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = { 2, 2, 1, 1, 1, 5 }; K=1
আউটপুট − K-এর চেয়ে বড় উপাদানধর্মী সাবঅ্যারে: ৪
ব্যাখ্যা − সাবঅ্যারে: [2], [2], [5], [2,2]। সব উপাদান ১-র চেয়ে বড়।
ইনপুট − arr[] = { 3,4,5,6 }; K=2
আউটপুট − K-এর চেয়ে বড় উপাদানধর্মী সাবঅ্যারে: ১০
ব্যাখ্যা − সাবঅ্যারে: [3], [4], [5], [6], [3,4], [4,5], [5,6], [3,4,5], [4,5,6], [3,4,5,6]। মোট ১০।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
for লুপ দিয়ে অ্যারে ট্রাভার্স করব। যদি বর্তমান উপাদান K-এর চেয়ে বড় হয়, count বাড়াব। অন্যথায় total += count*(count+1)/2 (সাবঅ্যারে সংখ্যা) এবং count=0 রিসেট করব। শেষে যদি count নন-জিরো থাকে, বাকি সাবঅ্যারে যোগ করব।
- অ্যারে
arr[]নিন। sub_greater_k(int arr[], int size, int k)ফাংশন অ্যারে এবং k নিয়ে K-র চেয়ে বড় উপাদানধর্মী সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক
count=0, total=0। i=0থেকেi<sizeপর্যন্ত লুপে:- যদি
arr[i] > k,count++। - অন্যথায়
total += count*(count+1)/2,count=0।
- যদি
- শেষে যদি
countনন-জিরো,total += count*(count+1)/2। totalরিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k) {
int count = 0;
int total = 0;
for (int i = 0; i < size; i++) {
if (arr[i] > k) {
count++;
} else {
total += (count) * (count + 1) / 2;
count = 0;
}
}
if (count) {
total += (count) * (count + 1) / 2;
}
return total;
}
int main() {
int arr[] = {2, 4, 6, 1, 3, 7, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 7;
cout << "Count of subarrays with all elements greater than K are: " << sub_greater_k(arr, size, k);
return 0;
}
আউটপুট
Count of subarrays with all elements greater than K are: 1
