এই সমস্যায়, আমাদের প্রতিটি n উপাদানের দুটি অ্যারে A এবং B দেওয়া হয়েছে। আমাদের কাজ হল অন্য অ্যারের সাথে একটি অ্যারের প্রতিটি উপাদানের সর্বাধিক সম্ভাব্য XOR খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা৷
অ্যারে বি এর সাথে অ্যারের প্রতিটি উপাদানের জন্য আমাদের সর্বোচ্চ XOR গণনা করতে হবে অর্থাৎ অ্যারের প্রতিটি উপাদানের জন্য আমরা অ্যারে বি-তে একটি উপাদান নির্বাচন করব যার সর্বোচ্চ XOR মান থাকবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক −
ইনপুট −
array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1} আউটপুট −
11 14 15 13
ব্যাখ্যা −
চলুন অ্যারের প্রতিটি উপাদানের XOR সংমিশ্রণটি অ্যারের B এর সমস্ত উপাদানের সাথে দেখি এবং তারপর প্রতিটির জন্য সর্বোচ্চ নির্বাচন করি৷
3 XOR 8 = 11 3 XOR 2 = 1 3 XOR 4 = 7 3 XOR 1 = 2 Maximum = 11. 6 XOR 8 = 14 6 XOR 2 = 4 6 XOR 4 = 2 6 XOR 1 = 1 Maximum = 14. 11 XOR 8 = 3 11 XOR 2 = 9 11 XOR 4 = 15 11 XOR 1 = 10 Maximum = 15. 9 XOR 8 = 1 9 XOR 2 = 11 9 XOR 4 = 13 9 XOR 1 = 8 Maximum = 13.
এই সমস্যাটি সমাধান করার জন্য, একটি সহজ এবং সরল পদ্ধতি হল সমস্ত সমন্বয় গণনা করা এবং উপরের উদাহরণে দেখানো হিসাবে সর্বাধিক XOR প্রিন্ট করা।
কিন্তু এটি কার্যকর হবে না কারণ কোডটি দুটি লুপের উপর নির্ভর করে যা O(n^2) এর ক্রমকে জটিল করে তোলে।
সুতরাং, আমরা সমস্যার একটি ভাল সমাধান দেখতে পাব।
এটি একটি ট্রাই ডেটা স্ট্রাকচার ব্যবহার করতে হবে যা অ্যারের A-এর সাথে মিলের জন্য অ্যারের B-এর সমস্ত উপাদানের বাইনারি সংরক্ষণ করবে, সর্বোচ্চ XOR খুঁজে বের করতে।
সুতরাং, অ্যারের একটি উপাদানের জন্য, আমরা এটির সবচেয়ে উল্লেখযোগ্য বিটটি পরীক্ষা করব এবং এটিকে 1 করার চেষ্টা করব। এবং পরবর্তী MSB-এ যান। এটি অনুসরণ করে আমরা অ্যারের B.
এ একটি উপাদানের জন্য আমাদের সর্বোচ্চ XOR উপাদান পাবউদাহরণ
অন্য অ্যারের সাথে একটি অ্যারের প্রতিটি উপাদানের সর্বাধিক সম্ভাব্য XOR খুঁজে বের করার জন্য প্রোগ্রাম
#include<iostream>
using namespace std;
struct trie{
int value;
trie *child[2];
};
trie * get(){
trie * root = new trie;
root -> value = 0;
root -> child[0] = NULL;
root -> child[1] = NULL;
return root;
}
void insert(trie * root, int key){
trie * temp = root;
for (int i = 31; i >= 0; i--){
bool current_bit = key & (1 << i);
if (temp -> child[current_bit] == NULL)
temp -> child[current_bit] = get();
temp = temp -> child[current_bit];
}
temp -> value = key;
}
int findMaxXor(trie * root, int element){
trie * temp = root;
for (int i = 31; i >= 0; i--){
bool bits = ( element & ( 1 << i) );
if (temp -> child[1 - bits] != NULL)
temp = temp -> child[1 - bits];
else
temp = temp -> child[bits];
}
return (element ^ temp -> value);
}
int main(){
int A[] = {3, 11, 6, 9};
int B[] = {8, 2, 4, 1};
int N = sizeof(A)/sizeof(A[0]);
trie * root = get();
for (int i = 0; i < N; i++)
insert(root, B[i]);
cout<<"The maximum possible XOR of every possible element in array A with Array B is\n";
for (int i = 0; i < N; i++)
cout <<findMaxXor(root, A[i])<<"\t";
return 0;
} আউটপুট
The maximum possible XOR of every possible element in array A with Array B is 11 15 14 13
