इस समस्या में, हमें 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) क्रम का बना देता है।
तो, हम समस्या का एक बेहतर समाधान देखेंगे।
यह ट्राई डेटा संरचना का उपयोग करना है जो एरे B के सभी तत्वों के बाइनरी को एरे A से मिलान के लिए संग्रहीत करेगा, ताकि अधिकतम XOR ढूंढा जा सके।
तो, एरे A के एक तत्व के लिए, हम इसके सबसे महत्वपूर्ण बिट की जांच करेंगे और इसे 1 बनाने का प्रयास करेंगे। और अगले MSB पर जाएंगे। इसका पालन करके हमें एरे B में एरे A के एक तत्व के लिए हमारा अधिकतम 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
