এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে N সংখ্যক সর্টেড ইন্টিজার মান আছে এবং একটি ইন্টিজার k। আমাদের কাজ হল সর্টেড অ্যারেতে k-র চেয়ে বড় এলিমেন্টের সংখ্যা বের করা।
উদাহরণ দেখি:
ইনপুট
arr[] = {1, 2, 5, 7, 8, 9} k = 4
আউটপুট
4
ব্যাখ্যা
k = 4-র চেয়ে বড় এলিমেন্টগুলো হল 5, 7, 8, 9
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল অ্যারেটি 0 থেকে N পর্যন্ত লুপ চালিয়ে প্রথম বড় এলিমেন্ট খুঁজে বের করা। তারপর বাকি এলিমেন্টের সংখ্যা কাউন্ট করা।
উদাহরণ
#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
