এই সমস্যায়, আমাদেরকে Q প্রশ্ন দেওয়া হয়েছে যেগুলির প্রত্যেকটি নিম্নলিখিত ধরণের একটি,
টাইপ 1 − সন্নিবেশ (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
