इस समस्या में, हमें n संख्याओं का एक ऐरे arr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो ऐरे के सभी सबएरे के XOR का योग निकाले।
उदाहरण से समझते हैं
इनपुट: arr[] = {5, 1, 4}
आउटपुट: 19
व्याख्या:
सबएरे के XOR:
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
योग = 5 + 1 + 4 + 4 + 5 + 0 = 19इस समस्या को हल करने का एक सरल तरीका नेस्टेड लूप का उपयोग करके सभी सबएरे ढूंढना है, फिर प्रत्येक सबएरे के तत्वों का XOR निकालकर योग में जोड़ना।
यह समाधान कुशल नहीं है क्योंकि इसमें लूप नेस्टेड हैं और इसकी समय जटिलता एक्सपोनेंशियल होगी।
कुशल दृष्टिकोण: प्रीफिक्स ऐरे
एक कुशल दृष्टिकोण प्रीफिक्स ऐरे का उपयोग करना है। यह प्रीफिक्स ऐरे इंडेक्स i तक सभी तत्वों के XOR को स्टोर करेगा।
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i]
इसके बाद, हम इंडेक्स i से j तक के तत्वों का XOR निकालने के लिए एक सरल सूत्र लागू कर सकते हैं।
XOR(i-j) = prefixarr[j] - prefixarr[i] (i >= 0 के लिए) यदि i = 0, तो XOR(i-j) = prefixarr[j]
इस सूत्र का उपयोग करके हम सभी सबएरे के XOR की गणना कर सकते हैं।
C++ प्रोग्राम उदाहरण
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all subarrays is " << calcSubArrayXORSum(arr, n);
return 0;
}आउटपुट
Sum of XOR of all subarrays is 46