এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যা এন সাজানো পূর্ণসংখ্যার মান এবং একটি পূর্ণসংখ্যা k নিয়ে গঠিত। আমাদের কাজ হল একটি সাজানো অ্যারেতে k-এর থেকে বড় উপাদানের সংখ্যা খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 2, 5, 7, 8, 9} k = 4 আউটপুট
4
ব্যাখ্যা
Elements greater than k = 4 are 5, 7, 8, 9
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল 0 থেকে N পর্যন্ত অ্যারের উপর একটি লুপ ব্যবহার করে। এবং তারপর k-এর থেকে বড় প্রথম উপাদানটিতে থামুন। তারপর অবশিষ্ট মানের সংখ্যা গণনা করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
for(int i = 0; i < n; i++){
if(arr[i] > k)
return (n - i);
}
return -1;
}
int main(){
int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
return 0;
} আউটপুট
The number of elements greater than k is 5
উপরের কোডটি ভাল কাজ করে কিন্তু প্রোগ্রামের সময় জটিলতা হল O(N)।
আরেকটি আরও কার্যকর পদ্ধতি হল k-এর থেকে বড় উপাদানগুলি খুঁজে বের করতে বাইনারি অনুসন্ধান ব্যবহার করা। এবং তারপর বৃহত্তর উপাদানের গণনা ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
int s = 0;
int e = n - 1;
int firstGreterEle = n;
while (s <= e) {
int mid = s + (e - s) / 2;
if (arr[mid] > k) {
firstGreterEle = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return (n - firstGreterEle);
}
int main(){
int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
return 0;
} আউটপুট
The number of elements greater than k is 5
