আমাদের একটি অ্যারে দেওয়া হয়েছে arr[] যাতে পূর্ণসংখ্যা উপাদান এবং একটি পরিবর্তনশীল k থাকে। লক্ষ্য হল arr[] এর সাবঅ্যারেগুলির গণনা খুঁজে বের করা যেখানে k এর থেকে সর্বাধিক/সর্বোচ্চ উপাদান রয়েছে। যদি অ্যারে হয় [1,2,3] এবং k হয় 1। তাহলে সম্ভাব্য সাবয়ারেগুলি হল [1], [2], [3], [1,2], [2,3], [1,2,3] ]। সর্বাধিক উপাদান> 1 সহ সাবয়ারে হল [2], [3], [1,2], [2,3], [1,2,3]। সুতরাং গণনা 5।
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − arr[] ={1,2,5,3 } k=3
আউটপুট − −6
-এর থেকে বেশি উপাদানের সর্বাধিক উপাদানের সংখ্যাব্যাখ্যা − সমস্ত সম্ভাব্য সাবয়ারে হল [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2, 5,3], [1,2,5,3]। এই অ্যারেগুলির মধ্যে সর্বাধিক 3টির বেশি উপাদান রয়েছে যার মধ্যে 5টি রয়েছে। সেগুলো হল -
[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]।
মোট 6টি সাব্যারে।
ইনপুট − arr[] ={1,2,3,4,5 } k=4
আউটপুট − −5
-এর থেকে বেশি উপাদানের সর্বাধিক উপাদানের সংখ্যাব্যাখ্যা − শুধুমাত্র 4 এর থেকে বড় উপাদান হল 5। 5 ধারণকারী সাবরে হবে −
[৫], [৪,৫], [৩,৪,৫], [২,৩,৪,৫], [১,২,৩,৪,৫]।
মোট 5টি সাব্যারে।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা জানি যে n উপাদান সহ অ্যারের সাবয়ারের মোট সংখ্যা হল n*(n+1)/2।
আমরা এখন এমন সাবয়ারের সন্ধান করব যেখানে
-
ইনপুট হিসাবে integer array arr[] এবং ভেরিয়েবল k নিন।
-
ফাংশন Max_k(int arr[], int size, int k) অ্যারে, k এবং অ্যারের দৈর্ঘ্য নেয় এবং সাবয়ারের গণনা প্রদান করে যার সর্বোচ্চ উপাদান k এর থেকে বেশি
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
যখন লুপ ব্যবহার করে, সূচী i=0 থেকে i
-
প্রতিটি উপাদানের জন্য যদি arr[i]>k একটি অবিরত বিবৃতি ব্যবহার করে এটি এড়িয়ে যান।
-
অন্যথায় একটি অভ্যন্তরীণ যখন লুপ ব্যবহার করে সাবয়ারের দৈর্ঘ্য গণনা শুরু করুন।
-
যদি arr[i]
-
ভিতরের শেষে যখন আমাদের বর্তমান সাবয়ারের দৈর্ঘ্য টেম্প হিসাবে থাকে।
temp*(temp+1)/2 গণনা করুন এবং গণনায় যোগ করুন।
-
এই ধরনের সব সাবয়ারের জন্য এটি করুন।
-
বাইরের শেষে যখন. আমাদের
-
অ্যার[] এর সম্ভাব্য সমস্ত সাবয়ারের সংখ্যা থেকে এই গণনাটি বিয়োগ করে গণনা আপডেট করুন, যা আকার*(আকার-1)/2।
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#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++;
}
int temp_2 = temp * (temp + 1);
count = count + temp_2 / 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
