এই সমস্যায়, আমাদের দুটি অ্যারে A এবং B দেওয়া আছে যাদের প্রত্যেকের n সংখ্যক উপাদান। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা একটি অ্যারেতে প্রতিটি উপাদানের সাথে অন্য অ্যারেতে সর্বোচ্চ সম্ভাব্য XOR বের করবে।
আমাদের অ্যারে A-এর প্রতিটি উপাদানের জন্য অ্যারে B-এর সাথে সর্বোচ্চ XOR কম্পিউট করতে হবে অর্থাৎ অ্যারে A-এর প্রতিটি উপাদানের জন্য অ্যারে B-এ একটি উপাদান নির্বাচন করব যেটির সাথে XOR ভ্যালু সর্বোচ্চ হবে।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই −
ইনপুট −
array A = {3, 6 ,11, 9} array B = {8, 2, 4, 1}
আউটপুট −
11 14 15 13
ব্যাখ্যা−
অ্যারে A-এর প্রতিটি উপাদানের সাথে অ্যারে B-এর সব উপাদানের XOR কম্বিনেশন দেখি এবং প্রতিটির জন্য সর্বোচ্চটি বেছে নিই।
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) আকারের করে দেয়।
তাই, আমরা একটি আরও ভালো সমাধান দেখব।
এটি হলো ট্রাই (trie) ডেটা স্ট্রাকচার ব্যবহার করা যেটি অ্যারে B-এর সব উপাদানের বাইনারি সংরক্ষণ করবে অ্যারে A-এর সাথে ম্যাচ করার জন্য, যাতে সর্বোচ্চ XOR বের করা যায়।
তবে, অ্যারে A-এর একটি উপাদানের জন্য, আমরা এর মোস্ট সিগনিফিক্যান্ট বিট চেক করব এবং সেটিকে ১ করার চেষ্টা করব। এবং তারপর নেক্সট MSB-এ যাব। এই পদ্ধতি অনুসরণ করে আমরা A-এর একটি উপাদানের জন্য 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
