समस्या कथन
सकारात्मक संख्याओं की एक सरणी गिरफ्तारी [] को देखते हुए, सरणी में सेटों की न्यूनतम संख्या ज्ञात करें जो निम्नलिखित संपत्ति को संतुष्ट करते हैं,
- एक समुच्चय में अधिकतम दो अवयव हो सकते हैं। दो तत्वों को सन्निहित होने की आवश्यकता नहीं है।
- सेट के तत्वों का योग दी गई कुंजी से कम या उसके बराबर होना चाहिए। यह माना जा सकता है कि दी गई कुंजी सबसे बड़े सरणी तत्व से बड़ी या उसके बराबर है।
उदाहरण
अगर arr[] ={1, 2, 3, 4} और k =5 तो निम्नलिखित 2 जोड़े बनाए जा सकते हैं -
{1, 4} और {2, 3}
एल्गोरिदम
- सरणी क्रमबद्ध करें
- सॉर्ट किए गए ऐरे के दो कोनों से दो पॉइंटर्स शुरू करें। यदि उनका योग दी गई कुंजी से छोटा या उसके बराबर है, तो हम उनका सेट बनाते हैं, अन्यथा हम केवल अंतिम तत्व पर विचार करते हैं
उदाहरण
#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
int i, j;
sort (arr, arr + n);
for (i = 0, j = n - 1; i <= j; ++i) {
if (arr[i] + arr[j] <= key) {
--j;
}
}
return i;
}
int main() {
int arr[] = {1, 2, 3, 4};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Minimum set = 2