এই সমস্যায়, আমাদের Q সংখ্যক কোয়েরি দেওয়া আছে যারা নিম্নলিখিত ধরণের হতে পারে:
- ধরণ ১ - ইনসার্শন (1, i) মান i-র এলিমেন্ট ডেটা স্ট্রাকচারে যোগ করতে।
- ধরণ ২ - findXOR (2, i), ডেটা স্ট্রাকচারের সব এলিমেন্টের সাথে i-এর XOR বের করতে।
ডেটা স্ট্রাকচারটি প্রাথমিকভাবে শুধু ০ মান ধারণ করবে।
উদাহরণ
ইনপুট
Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)
আউটপুট
15 15
ব্যাখ্যা
প্রতিটি কোয়েরি সমাধান:
(1, 9) => ডেটা স্ট্রাকচার => {9}
(1, 3) => ডেটা স্ট্রাকচার => {9, 3}
(1, 7) => ডেটা স্ট্রাকচার => {9, 3, 7}
(2, 8) => সর্বোচ্চ XOR(_, 8) = 15, XOR(7, 8)
(1, 5) => ডেটা স্ট্রাকচার => {9, 3, 7, 5}
(2, 12) => সর্বোচ্চ XOR(_, 12) = 15, XOR(3, 12)
সমাধানের পদ্ধতি
সমস্যাটি সমাধান করা যায় ট্রাই (Trie) ডেটা স্ট্রাকচার ব্যবহার করে, যা একটি বিশেষ ধরনের সার্চ ট্রি। আমরা এমন একটি ট্রাই ব্যবহার করব যাতে প্রতিটি নোডের দুটি চাইল্ড নোড থাকে বাইনারি মান সংরক্ষণ করার জন্য। ধরণ ১ কোয়েরির জন্য নম্বরটির বাইনারি মান ট্রাই-তে যোগ করব। ধরণ ২ কোয়েরির জন্য দেওয়া মানের জন্য ট্রাই-তে পথ খুঁজে বের করব এবং লেভেল কাউন্ট থেকে ফলাফল পাব।
ট্রাই ডেটা স্ট্রাকচার সম্পর্কে আরও জানতে, ট্রাই ডেটা স্ট্রাকচার ভিজিট করুন।
C++ প্রোগ্রাম উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct Trie {
Trie* children[2];
bool isLeaf;
};
bool check(int N, int i) {
return (bool)(N & (1<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
