समस्या विवरण
सकारात्मक संख्याओं का एक ऐरे arr[] दिया गया है, ऐरे में न्यूनतम संख्या में सेट ढूंढें जो निम्नलिखित गुण को संतुष्ट करते हैं:
- एक सेट में अधिकतम दो एलिमेंट्स हो सकते हैं। दोनों एलिमेंट्स का सन्निकट होना आवश्यक नहीं है।
- सेट के एलिमेंट्स का योग दी गई Key से कम या बराबर होना चाहिए। यह माना जा सकता है कि दी गई key सबसे बड़े ऐरे एलिमेंट से अधिक या बराबर है।
उदाहरण
यदि arr[] = {1, 2, 3, 4} और k = 5 तो निम्नलिखित 2 जोड़े बनाए जा सकते हैं -
{1, 4} और {2, 3}
एल्गोरिदम
- ऐरे को सॉर्ट करें
- सॉर्ट किए गए ऐरे के दो कोनों से दो पॉइंटर्स शुरू करें। यदि उनका योग दी गई key से कम या बराबर है, तो हम उनका सेट बनाते हैं, अन्यथा हम अंतिम एलिमेंट को अकेले मानते हैं
उदाहरण
#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
