इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है। हमारा काम एक प्रोग्राम बनाना है जो एक सरणी में सभी जोड़ियों के योग के XOR का योग ज्ञात करे।
आइए समस्या को समझने के लिए एक उदाहरण देखें,
इनपुट: गिरफ्तारी[5, 7, 9]
आउटपुट: 22
स्पष्टीकरण:
(5+5) ^ (5+7) ^ (5+9) ^ (7+5) ^ (7+7) ^ (7+9) ^ (9+5) ^ (9+7) ^ (9+9) =22
नेस्टेड लूप का उपयोग करके समस्या का एक सरल समाधान है। और सरणी से सभी संभावित जोड़े बनाना। और प्रत्येक जोड़ी के योग के XOR की गणना करें।
एल्गोरिदम:
प्रारंभ XorSum =0
चरण 1: 0 से n तक पुनरावृति। अनुसरण करें:
चरण 1.1: 0 से n तक पुनरावृति। अनुसरण करें
चरण 1.1.1: अपडेट XorSum यानी XorSum =XorSum ^ (arr[i]+arr[j]).
चरण 2: वापसी राशि
हमारे कोड की कार्यप्रणाली को दर्शाने वाला प्रोग्राम
उदाहरण
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
XorSum = XorSum^(arr[i]+arr[j]);
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} आउटपुट
XOR of sum of all pairs in an array is 22
यह समाधान कुशल नहीं है क्योंकि इसकी समय जटिलता क्रम की है n 2 ।
एक कुशल समाधान XOR के गुणों का उपयोग कर रहा है। समस्या को हल करने के लिए, हम सरणी के सभी तत्वों के XOR की गणना करेंगे और फिर इसे दो से गुणा करेंगे।
एल्गोरिदम:
XorSum =0 को प्रारंभ करें
चरण 1: 0 से n तक पुनरावृति करें।
चरण 1.1: अपडेट XorSum यानी XorSum =XorSum ^ arr[i]
चरण 2: राशि को दोगुना करें और उसे वापस कर दें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
XorSum = XorSum^arr[i];
XorSum = 2*XorSum;
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} आउटपुट
XOR of sum of all pairs in an array is 22