समस्या विवरण
n इंटीजर्स का एक सेट दिया गया है, न्यूनतम संख्या में ऑपरेशन्स (आप सेट में एलिमेंट्स इन्सर्ट/डिलीट कर सकते हैं) करके सेट के MEX को x के बराबर बनाएं (जो दिया गया है)।
नोट - एक इंटीजर्स सेट का MEX वह न्यूनतम नॉन-नेगेटिव इंटीजर है जो उसमें मौजूद नहीं है। उदाहरण के लिए, सेट {0, 2, 4} का MEX 1 है और सेट {1, 2, 3} का MEX 0 है।
उदाहरण
यदि n = 5 और x = 3 और ऐरे है {0, 4, 5, 6, 7} तो हमें न्यूनतम 2 ऑपरेशन्स की आवश्यकता है।
एल्गोरिदम
- दृष्टिकोण यह देखना है कि अंतिम सेट में x से कम सभी एलिमेंट्स मौजूद होने चाहिए, x मौजूद नहीं होना चाहिए और x से बड़ा कोई भी एलिमेंट मायने नहीं रखता।
- इसलिए, हम उन एलिमेंट्स की संख्या गिनेंगे जो x से कम हैं लेकिन प्रारंभिक सेट में मौजूद नहीं हैं और इसे उत्तर में जोड़ देंगे।
- यदि x मौजूद है तो हम उत्तर में 1 जोड़ देंगे क्योंकि x को हटाया जाना चाहिए।
उदाहरण
#include <iostream>
using namespace std;
int getMinOperations(int *arr, int n, int x) {
int k = x, i = 0;
while (n--) {
if (arr[n] < x) {
--k;
}
if (arr[n] == x) {
++k;
}
}
return k;
}
int main() {
int arr[] = {0, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout << "Minimum required operations = " << getMinOperations(arr, n, x) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है:
Minimum required operations = 2
