इस समस्या में, हमें n तत्वों के दो सरणियाँ A और B दिए गए हैं। हमारा काम एक प्रोग्राम बनाना है जो किसी ऐरे में हर एलीमेंट के अधिकतम संभव XOR को दूसरे ऐरे के साथ ढूँढ़ने के लिए है।
हमें सरणी A के प्रत्येक तत्व के लिए सरणी B के साथ अधिकतम XOR की गणना करनी होगी अर्थात सरणी A के प्रत्येक तत्व के लिए हम सरणी B में एक तत्व का चयन करेंगे जिसका अधिकतम XOR मान होगा।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट -
array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1} आउटपुट -
11 14 15 13
स्पष्टीकरण -
आइए सरणी A के प्रत्येक तत्व के 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 के एक तत्व के लिए, हम इसके सबसे महत्वपूर्ण बिट की जाँच करेंगे और इसे 1 बनाने का प्रयास करेंगे। और अगले MSB पर जाएँ। इसके बाद हम ए के एक तत्व के लिए एरे बी में अपना अधिकतम एक्सओआर तत्व प्राप्त करेंगे।
उदाहरण
किसी अन्य सरणी के साथ एक सरणी में प्रत्येक तत्व के अधिकतम संभव 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