समस्या कथन
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