संख्याओं का XOR जो C++ में दी गई श्रेणी में सम संख्या में दिखाई देता है

इस समस्या में, हमें n तत्वों की एक सरणी दी गई है और कुछ प्रश्न हैं जो सरणी में प्रारंभ बिंदु से अंत बिंदु तक हैं। हमारा काम दो तत्वों का एक्सओआर ढूंढना है जो सीमा में कई बार भी दिखाई देते हैं।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट -

array = {1, 2, 3, 1, 1, 2, 2, 3}
querries = 2
R = 4
L = 2, R = 5
L = 2, R = 7

आउटपुट -

0
1
0

इस समस्या का समाधान काफी आसान है, हम प्रत्येक क्वेरी द्वारा दी गई सीमा के भीतर सरणी के सभी तत्वों के एक्सओआर का योग पाएंगे। इसके लिए हम उपसर्ग योग xor का उपयोग करेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

#include <bits/stdc++.h>
using namespace std;
struct que {
   int L, R, idx;
};
bool cmp(que a, que b){
   if (a.R != b.R)
      return a.R < b.R;
   else
      return a.L < b.L;
}
int findXORSum(int BIT[], int index){
   int xorSum = 0;
   index = index + 1;
   while (index > 0){
      xorSum ^= BIT[index];
      index -= index & (-index);
   }
   return xorSum;
}
void updateBIT(int BIT[], int N, int index, int val){
   index = index + 1;
   while (index <= N){
      BIT[index] ^= val;
      index += index & (-index);
   }
}
int* createBitTree(int arr[], int N){
   int* BIT = new int[N + 1];
   for (int i = 1; i <= N; i++)
      BIT[i] = 0;
   return BIT;
}
void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]){
   int* prefixXOR = new int[N + 1];
   map<int, int> XORval;
   for (int i = 0; i < N; i++) {
      if (!XORval[arr[i]])
         XORval[arr[i]] = i;
      if (i == 0)
         prefixXOR[i] = arr[i];
      else
         prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
   }
   int lastOcc[1000001];
   memset(lastOcc, -1, sizeof(lastOcc));
   sort(queries, queries + Q, cmp);
   int res[Q];
   int j = 0;
   for (int i = 0; i < Q; i++){
      while (j <= queries[i].R){
         if (lastOcc[XORval[arr[j]]] != -1)
            updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
         updateBIT(BIT, N, j, arr[j]);
         lastOcc[XORval[arr[j]]] = j;
         j++;
      }
      int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
      int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
      res[queries[i].idx] = allXOR ^ distinctXOR;
   }
   for (int i = 0; i < Q; i++)
      cout << res[i] << endl;
}
int main() {
   int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   int* BIT = createBitTree(arr, N);
   que queries[4];
   queries[0].L = 1;
   queries[0].R = 4; queries[0].idx = 0;
   queries[1].L = 2;
   queries[1].R = 7, queries[1].idx = 1;
   queries[2].L = 0;
   queries[2].R = 3, queries[2].idx = 2;
   queries[3].L = 3;
   queries[3].R = 6, queries[3].idx = 3;
   int Q = sizeof(queries) / sizeof(queries[0]);
   cout<<"Xor sum for all queries is \n";
   findXORSolution(arr, N, queries, Q, BIT);
   return 0;
}

आउटपुट

Xor sum for all queries is
3
2
0
2