इस समस्या में, हमें एक सरणी arr [] दिया जाता है जिसमें N क्रमबद्ध पूर्णांक मान और एक पूर्णांक 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