इस समस्या में, हमें n संख्याओं का एक सरणी arr[] दिया जाता है। हमारा कार्य सरणी के सभी उप-सरणी के XOR का योग ज्ञात करने के लिए एक प्रोग्राम बनाना है।
यहां, हमें दिए गए सरणी के सभी उप-सरणी खोजने की आवश्यकता है, और फिर प्रत्येक उप-सरणी के लिए, हम तत्व का xor ढूंढेंगे और योग चर में XOR मान जोड़ेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
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
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19 इस समस्या को हल करने का एक आसान तरीका सभी सबएरे को खोजने के लिए अगले लूप का उपयोग कर रहा है। फिर उप-सरणी के तत्वों का XOR ढूँढना और योग चर में जोड़ना।
यह समाधान कुशल नहीं है क्योंकि यह लूप के नेस्टिंग का उपयोग करता है और इसमें घातीय समय जटिलता होगी।
इस समस्या को हल करने के लिए एक कुशल तरीका उपसर्ग सरणी का उपयोग कर रहा है। यह उपसर्ग सरणी सरणी के सभी तत्वों के xor को i तक संग्रहीत करेगा। यानी,
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
इसके बाद, हम सूचकांक i से j तक के तत्वों का XOR ज्ञात करने के लिए एक सरल सूत्र लागू कर सकते हैं।
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
इस सूत्र का उपयोग करके हम सभी उपसरणियों का XOR पाएंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#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