इस समस्या में, हमें Q प्रश्न दिए गए हैं जिनमें से प्रत्येक निम्न प्रकार में से एक है,
टाइप 1 - अपनी डेटा संरचना में मान i के साथ तत्व जोड़ने के लिए प्रविष्टि (1, i)।
टाइप 2 - FindXOR (2, i), तत्व i के साथ डेटा संरचना के सभी तत्वों के XOR को खोजने के लिए।
डेटा संरचना में प्रारंभ में केवल 1 तत्व होना चाहिए जो कि 0 होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)
आउटपुट
15 15
स्पष्टीकरण
Solving each query,
(1, 9) => data structure => {9}
(1, 3) => data structure => {9, 3}
(1, 7) => data structure => {9, 3, 7}
(2, 8) => maximum XOR(_, 8) = 15, XOR(7, 8)
(1, 5) => data structure => {9, 3, 7, 5}
(2, 12) => maximum XOR(_, 12) = 15, XOR(3, 12) समाधान दृष्टिकोण
समस्या का समाधान ट्राई डेटा संरचना का उपयोग करके पाया जा सकता है, जो एक विशेष प्रकार का खोज ट्री है। हम एक ट्री का उपयोग करेंगे जिसमें प्रत्येक नोड में किसी संख्या के बाइनरी मानों को संग्रहीत करने के लिए दो चाइल्ड नोड होते हैं। इसके बाद हम टाइप 1 की प्रत्येक क्वेरी के लिए संख्या के बाइनरी मान को ट्री में जोड़ देंगे। टाइप 2 की एक क्वेरी के लिए, हम दिए गए मान के लिए ट्राई में पथ पाएंगे और फिर लेवल काउंट परिणाम देगा।
ट्राइ विज़िट पर अधिक जानकारी के लिए, डेटा संरचना आज़माएं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct Trie {
Trie* children[2];
bool isLeaf;
};
bool check(int N, int i) {
return (bool)(N & (1<<i));
}
Trie* newNode() {
Trie* temp = new Trie;
temp->isLeaf = false;
temp->children[0] = NULL;
temp->children[1] = NULL;
return temp;
}
void insertVal(Trie* root, int x) {
Trie* val = root;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if (! val->children[f])
val->children[f] = newNode();
val = val->children[f];
}
val->isLeaf = true;
}
int solveQueryType2(Trie *root, int x){
Trie* val = root;
int ans = 0;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if ((val->children[f ^ 1])){
ans = ans + (1 << i);
val = val->children[f ^ 1];
}
else
val = val->children[f];
}
return ans;
}
void solveQueryType1(Trie *root, int x){
insertVal(root, x);
}
int main(){
int Q = 6;
int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
Trie* root = newNode();
for(int i = 0; i < Q; i++){
if(query[i][0] == 1 ){
solveQueryType1(root, query[i][1]);
cout<<"Value inserted to the data Structure. value =
"<<query[i][1]<<endl;
}
if(query[i][0] == 2){
cout<<"The maximum XOR with "<<query[i][1]<<" is
"<<solveQueryType2(root, query[i][1])<<endl;
}
}
return 0;
} आउटपुट
Value inserted to the data Structure. value = 9 Value inserted to the data Structure. value = 3 Value inserted to the data Structure. value = 7 The maximum XOR with 8 is 15 Value inserted to the data Structure. value = 5 The maximum XOR with 12 is 15