इस समस्या में, हमें n पूर्णांकों का एक ऐरे arr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो ऐरे में सभी जोड़ियों के XOR का योग निकाले।
उदाहरण से समझते हैं
इनपुट: arr[] = {5, 1, 4}
आउटपुट: 10
व्याख्या:
सभी जोड़ियों का योग:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
योग = 4 + 5 + 1 = 10इस समस्या को हल करने का एक सरल दृष्टिकोण नेस्टेड लूप चलाकर सभी संख्याओं की जोड़ियां ढूंढना है। प्रत्येक जोड़ी का XOR निकालें और उन्हें योग में जोड़ें।
एल्गोरिदम
sum = 0 से आरंभ करें
चरण 1: i = 0 से n तक लूप चलाएं:
चरण 1.1: j = i से n तक लूप चलाएं:
चरण 1.1.1: sum अपडेट करें, यानी sum += arr[i] ^ arr[j]
चरण 2: sum वापस करेंC++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)
#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
sum += (arr[i] ^ arr[j]);
return sum;
}
int main() {
int arr[] = { 5, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all pairs in an array is " << findXORSum(arr, n);
return 0;
}आउटपुट
Sum of XOR of all pairs in an array is 10
इस एल्गोरिदम की समय जटिलता O(n²) है और यह समस्या का सबसे कुशल समाधान नहीं है।
कुशल समाधान: बिट मैनिपुलेशन तकनीक
एक कुशल समाधान बिट मैनिपुलेशन तकनीक का उपयोग करना है।
यहां, हम संख्या के बिट्स पर विचार करेंगे और प्रत्येक पोजीशन पर। और नीचे दिए गए सूत्र को लागू करके मध्यवर्ती योग निकालेंगे:
(सेट बिट्स की संख्या) * (अनसेट बिट्स की संख्या) * (2^(बिट_पोजीशन))
अंतिम योग निकालने के लिए, हम सभी बिट्स के मध्यवर्ती योग को जोड़ेंगे।
हमारा समाधान 64-बिट पूर्णांक मान के लिए है। इस दृष्टिकोण के लिए, हमें बिट्स की संख्या चाहिए।
एल्गोरिदम
sum = 0, setBits = 0, unsetBits = 0 से आरंभ करें चरण 1: i = 0 से 64 तक लूप चलाएं, चरण 2, 3 दोहराएं चरण 2: setBits और unsetBits को 0 पर रीसेट करें चरण 3: ऐरे के प्रत्येक तत्व के लिए i-वीं पोजीशन पर setBits और unsetBits का मान निकालें चरण 4: sum += (setBits * unsetBits * (2^i)) से अपडेट करें
C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण)
#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
long sum = 0;
int unsetBits = 0, setBits = 0;
for (int i = 0; i < 32; i++) {
unsetBits = 0; setBits = 0;
for (int j = 0; j < n; j++) {
if (arr[j] % 2 == 0)
unsetBits++;
else
setBits++;
arr[j] /= 2;
}
sum += (unsetBits * setBits * (pow(2, i)));
}
return sum;
}
int main() {
int arr[] = { 5, 1, 4, 7, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all pairs in an array is " << findXORSum(arr, n);
return 0;
}आउटपुट
Sum of XOR of all pairs in an array is 68
