समस्या विवरण
हमें n एलिमेंट्स का एक ऐरे दिया गया है। कार्य पूरे ऐरे का XOR 0 बनाना है। हम इसे प्राप्त करने के लिए निम्नलिखित कर सकते हैं।
हम किसी एक एलिमेंट का चयन कर सकते हैं -
- एलिमेंट का चयन करने के बाद, हम इसे 1 से बढ़ा या घटा सकते हैं।
- हमें चयनित एलिमेंट के लिए पूरे ऐरे के XOR योग को शून्य बनाने के लिए आवश्यक न्यूनतम इन्क्रीमेंट/डिक्रीमेंट ऑपरेशन्स की संख्या ढूंढनी होगी।
उदाहरण
यदि arr[] = {2, 4, 7} तो 1 ऑपरेशन आवश्यक है -
- एलिमेंट 2 का चयन करें
- इसे 1 से घटाएं
- अब ऐरे {3, 4, 7} बन जाता है और इसका XOR 0 है
एल्गोरिदम
- पूरे ऐरे का XOR ढूंढें
- अब, मान लें कि हमने एलिमेंट arr[i] चुना है, तो उस एलिमेंट के लिए आवश्यक लागत निरपेक्ष(arr[i] - (XORsum ^ arr[i])) होगी
- प्रत्येक एलिमेंट के लिए इन निरपेक्ष मानों का न्यूनतम निकालना हमारा न्यूनतम आवश्यक ऑपरेशन होगा
उदाहरण
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getMinCost(int *arr, int n) {
int operations = INT_MAX;
int elem;
int xorValue = 0;
for (int i = 0; i < n; ++i) {
xorValue = xorValue ^ arr[i];
}
for (int i = 0; i < n; ++i) {
if (operations > abs((xorValue ^ arr[i]) - arr[i])) {
operations = abs((xorValue ^ arr[i]) - arr[i]);
elem = arr[i];
}
}
cout << "Element= " << elem << endl;
cout << "Minimum required operations = " << abs(operations) << endl;
}
int main() {
int arr[] = {2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
getMinCost(arr, n);
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है:
Element = 2 Minimum required operations = 1
