समस्या कथन
हमें n तत्वों की एक सरणी दी गई है। कार्य संपूर्ण सरणी 0 का XOR बनाना है। इसे प्राप्त करने के लिए हम निम्नलिखित कार्य कर सकते हैं।
हम किसी एक तत्व का चयन कर सकते हैं -
- तत्व का चयन करने के बाद, हम इसे 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