इस समस्या में, हमें एक गिरफ्तारी [] और कुछ प्रश्न दिए गए हैं जो सरणी में एल से आर के बीच हैं। हमारा काम एल से आर के बीच सबएरे के एक्सओआर को प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी ={1, 4, 5, 7, 2, 9} एल =1, आर =5
आउटपुट -
स्पष्टीकरण − 4^5^7^2^9
-
इस समस्या को हल करने के लिए, हम निम्नलिखित अवलोकन के आधार पर एक सरणी बनाएंगे,
-
हम XOR कई बिट्स करेंगे, यदि 1s की विषम संख्या है, तो परिणाम 1 होगा अन्यथा परिणाम 0 होगा।
अब, हम एक द्वि-आयामी ऐरे काउंट बनाएंगे जो 1s की गिनती को स्टोर करेगा। मान गणना [i] [j] स्थिति i-j के लिए 1s की संख्या की संख्या है जो कि 1 की संख्या है जो बिट की ith स्थिति में सबअरे गिरफ्तारी [0..j] में मौजूद हैं। उप-सरणी गिरफ्तारी [L..R] के सभी बिट्स के लिए 1s की संख्या गिनती सरणी का उपयोग करके पाई जाती है। गिरफ्तार करने का सूत्र [एल ... आर] =गिनती [i] [आर] - गिनती [i] [एल -1]। यदि 1s की संख्या विषम है, तो ith बिट परिणाम में सेट होता है। अंतिम परिणाम ith बिट के अनुरूप 2 की शक्ति को जोड़कर प्राप्त किया जा सकता है, बशर्ते कि यह बिट सेट हो।
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
उदाहरण
#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