इस समस्या में, हमें आकार n का एक ऐरे arr[] दिया गया है। हमारा कार्य ऐरे में सभी जोड़ियों के योग के XOR का योग खोजने के लिए एक प्रोग्राम बनाना है।
एक उदाहरण देखकर समस्या को समझते हैं,
इनपुट: arr[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
यह समाधान कुशल नहीं है क्योंकि इसकी समय जटिलता n2 कोटि की है।
एक कुशल समाधान 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
