दिए गए रेंज में मौजूद सभी सबएरे के XOR की गणना करना और इसे प्रिंट करना। उदाहरण के लिए:
इनपुट: arr[] = {4, 1, 2, 3, 5}, Q = 3
क्वेरी q1 = {1, 2}
q2 = {2, 4}
q3 = {1, 4}
आउटपुट: 0 2 0
व्याख्या: जैसा कि दी गई समस्या में कहा गया है कि हमें दिए गए रेंज में मौजूद सभी सबएरे के XOR को खोजने की आवश्यकता है इसलिए क्वेरी 2 के लिए सबएरे हैं: {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}
तो जैसा कि आप देख सकते हैं तत्वों की घटनाओं की संख्या हैं:
1, 3 बार मौजूद है
2, 4 बार मौजूद है
3, 3 बार मौजूद है
अब जैसा कि हम XOR का गुण जानते हैं कि जो संख्याएं सम संख्या में मौजूद हैं वे कैंसिल हो जाती हैं इसलिए 2 कैंसिल हो गया और सिर्फ 3 और 1 का XOR रह गया और वह हमारा उत्तर था।
हमें इस समस्या में बन रहे पैटर्न को देखना होगा, और फिर इसे तदनुसार लागू करना होगा।
समाधान खोजने का दृष्टिकोण
इस समस्या में, हम समस्या में मौजूद बीच के पैटर्न को खोजने की कोशिश कर रहे हैं। जब हम उस पैटर्न को देखते हैं, तो हम इसे तदनुसार लागू करते हैं और परिणामों की जांच करते हैं।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r) {
if ((r - l + 1) % 2 == 0) // यदि रेंज में मौजूद तत्वों की संख्या सम है
cout << "0";
else {
if (l % 2 == 0) // यदि l सम है
cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
else // यदि l विषम है
cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
}
}
int main() {
int arr[] = {4, 1, 2, 3, 5};
int n = sizeof(arr) / sizeof(int); // हमारे एरे का आकार
int l[] = {1, 2, 1}; // दी गई क्वेरी का बायां इंडेक्स
int r[] = {2, 4, 4}; // दी गई क्वेरी का दायां इंडेक्स
int q = sizeof(l) / sizeof(int); // पूछी गई क्वेरी की संख्या
// सम और विषम इंडेक्स के लिए अलग-अलग प्रीफिक्स XOR
int prefodd[n] = {0}, prefeven[n] = {0};
for (int i = 1; i <= n; i++) {
if ((i) % 2 == 0) { // यदि i सम है तो हम prefeven बदलते हैं
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
} else {
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
for (int i = 0; i < q; i++) {
ansQueries(prefeven, prefodd, l[i], r[i]);
}
return 0;
}
आउटपुट
0 2 0
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम पहले देखते हैं कि यदि हमारी रेंज का आकार सम है तो हमारा उत्तर शून्य होगा क्योंकि जब हम सभी सबएरे प्रिंट करते हैं तो हर संख्या सम बार दिखाई देती है इसलिए उनका XOR लेने पर उत्तर बस 0 होगा। अब हमारे अगले भाग के लिए जहां रेंज का आकार विषम है, इस मामले में जो संख्या विषम बार दिखाई देती है वह दी गई रेंज में सम स्थिति में होती है और हमारा उत्तर बस दी गई रेंज में सम स्थिति पर दिखाई देने वाली संख्याओं के XORs होंगे। हम दो प्रीफिक्स एरे बनाए रखते हैं जिनमें वैकल्पिक स्थितियों के XOR होते हैं क्योंकि हमारा prefeven सभी सम इंडेक्स के XOR को समाहित करता है और prefodd सभी विषम इंडेक्स के XOR को समाहित करता है। अब जब हम एक क्वेरी हल करते हैं तो हमें बस यह जांचना होगा कि हमारा l सम है या विषम और तदनुसार अपना उत्तर देना होगा।
निष्कर्ष
इस ट्यूटोरियल में, हम सभी सबएरे के XOR के XOR पर क्वेरी को हल करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।