इस समस्या में, हमें एक arr[] और कुछ क्वेरीज दी गई हैं जो सरणी में L से R तक की रेंज हैं। हमारा कार्य L से R के बीच सबएरे का XOR प्रिंट करना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट - array = {1, 4, 5, 7, 2, 9} L = 1, R = 5
आउटपुट -
व्याख्या - 4^5^7^2^9
इस समस्या को हल करने के लिए, हम निम्न अवलोकन के आधार पर एक सरणी बनाएंगे,
हम कई बिट्स का XOR करेंगे, यदि 1s की संख्या विषम है, तो परिणाम 1 होगा अन्यथा परिणाम 0 है।
अब, हम एक दो-आयामी सरणी count बनाएंगे जो 1s की गिनती संग्रहीत करेगी। count[i][j] का मान i-j स्थिति के लिए 1s की गिनती है जो सबएरे arr[0..j] में बिट के i-th स्थान पर मौजूद 1s की संख्या है। सब-एरे arr[L..R] के सभी बिट्स के लिए 1s की संख्या count सरणी का उपयोग करके पाई जाती है। arr[L...R] खोजने का सूत्र = count[i][R] - count[i][L-1]। यदि 1s की संख्या विषम है, तो i-th बिट परिणाम में सेट है। अंतिम परिणाम 2 की घात के योग से प्राप्त किया जा सकता है जो i-th बिट से मेल खाता है बशर्ते यह सेट बिट हो।
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int>>& cnt) {
int i, j;
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
cnt[i][j] = cnt[i][j - 1];
}
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int>> count) {
int result = 0;
int noOfOnes;
int i, j;
for (i = 0; i < 32; i++) {
noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1) {
result += (1 << i);
}
}
return result;
}
int main() {
int arr[] = {1, 4, 5, 7, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int>> count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1;
int R = 5;
cout << "The XOR of SubArray: " << findXORofSubArray(L, R, count);
return 0;
}
आउटपुट
The XOR of SubArray: 13
