सरणी में दो तत्व जिनके xor अधिकतम

Question

पूर्णांक की एक श्रृंखला को देखते हुए, आपको दो तत्वों को ढूंढना होगा जिनके एक्सओआर अधिकतम हैं।

प्रत्येक तत्व को चुनकर और अन्य तत्वों के साथ xoring करके और फिर जोड़ी को खोजने के लिए परिणामों की तुलना करके निष्पक्ष दृष्टिकोण - सही है।

इसके अलावा, क्या कोई कुशल एल्गोरिदम है?

Answer 1

मुझे लगता है कि मेरे पास ओ (एन एलजी यू) एल्गोरिदम है, जहां यू सबसे बड़ी संख्या है। विचार उपयोगकर्ता 9 4 9 300 के समान है, लेकिन थोड़ी अधिक जानकारी के साथ।

अंतर्ज्ञान निम्नानुसार है।जब आप अधिकतम संख्या प्राप्त करने के लिए दो नंबरों को एक साथ जोड़ रहे हैं, तो आप उच्चतम संभावित स्थिति पर 1 चाहते हैं, और उसके बाद जोड़ी इस स्थिति में 1 है, तो आप अगले में 1 के साथ एक जोड़ी चाहते हैं संभव उच्चतम स्थिति, आदि

तो एल्गोरिदम निम्नानुसार है। संख्याओं में कहीं भी उच्चतम 1 बिट ढूंढकर शुरू करें (आप ओ (एलजी यू) प्रत्येक एन संख्याओं के अनुसार ओ (एलजी यू) काम करके समय में ऐसा कर सकते हैं। अब, सरणी को दो टुकड़ों में विभाजित करें - उन संख्याओं में से एक जिनमें उस बिट में 1 है और समूह उस बिट में 0 है। किसी भी इष्टतम समाधान को उस स्थान पर 0 के साथ पहले स्थान पर एक नंबर के साथ एक संख्या जोड़नी चाहिए, क्योंकि उस स्थान पर 0 बिट जितना अधिक होगा। किसी भी अन्य जोड़ी में 0 है।

अब, संक्षेप में, हम 1 और 0 समूह से संख्याओं की जोड़ी ढूंढना चाहते हैं जिनमें उनमें से सबसे ज्यादा 1 है। ऐसा करने के लिए इन दोनों समूहों की, उन्हें चार समूहों में विभाजित: 11

नंबर के साथ शुरू 10

नंबर के साथ शुरू

• नंबर 01
• नंबर के साथ शुरू 00

के साथ शुरू

यदि 11 और 00 समूह में या 10 और 01 समूहों में कोई संख्या है, तो उनका एक्सओआर आदर्श होगा (11 से शुरू होगा)। नतीजतन, यदि समूहों के उन जोड़े में से कोई भी खाली नहीं है, तो उन समूहों से आदर्श समाधान की पुनरावृत्ति गणना करें, फिर उन उपप्रोबम समाधानों में से अधिकतम को वापस करें। अन्यथा, यदि दोनों समूह खाली हैं, तो इसका मतलब है कि सभी संख्याओं में उनकी दूसरी स्थिति में एक ही अंक होना चाहिए। नतीजतन, 1 से शुरू होने वाली संख्या का इष्टतम एक्सओआर और 0 से शुरू होने वाला नंबर अगले दूसरे बिट को रद्द कर देगा, इसलिए हमें केवल तीसरे बिट को देखना चाहिए।

• को देखते हुए समूह 1 और समूह 0 और थोड़ा सूचकांक मैं:

  • यह निम्न पुनरावर्ती एल्गोरिदम कि, उनके MSB से विभाजित संख्या के दो समूहों के साथ शुरू कर देता है, इस सवाल का जवाब देता है यदि बिट इंडेक्स बिट्स की संख्या के बराबर है, तो 1 समूह में (अद्वितीय) संख्या का एक्सओआर और 0 समूह में (अद्वितीय) संख्या लौटाएं।

  • उन समूहों से समूह 11, 10, 01, और 00 का निर्माण करें।
  • यदि समूह 11 और समूह 00 अपरिवर्तनीय हैं, तो मैं दो समूहों से अधिकतम एक्सओआर को दोहराता हूं I + 1.
  • यदि समूह 10 और समूह 01 अस्वीकार्य हैं, तो उन दो समूहों के अधिकतम XOR को पुनः मिलाकर, बिट I + 1.
  • से शुरू होने पर यदि उपर्युक्त जोड़ों में से कोई भी संभव था, तो रिकर्सन द्वारा प्राप्त अधिकतम जोड़ी को वापस करें।
  • अन्यथा, संख्या के सभी स्थिति मैं में एक ही सा है, तो पाया अधिकतम जोड़ी लौट बिट को देखकर चाहिए i + 1 समूह 1 पर और 0.

शुरू करने के लिए एल्गोरिदम, आप वास्तव में शुरुआती समूह से संख्याओं को दो समूहों में विभाजित कर सकते हैं - एमएसबी 1 के साथ संख्याएं और एमएसबी 0 के साथ संख्याएं। फिर आप उपरोक्त एल्गोरिदम को संख्याओं के दो समूहों के साथ एक रिकर्सिव कॉल को आग लगाना चाहते हैं।

उदाहरण के तौर पर, संख्या 5 1 4 3 0 2 पर विचार करें।

101 100 
001 011 000 010 

अब, हम उपरोक्त एल्गोरिथ्म लागू होते हैं: इन प्रतिवेदनों

101 001 100 011 000 010 

हम उन्हें 1 समूह में विभाजित करके शुरू और 0 समूह है। हम 11 समूहों, 10, 01 में इस विभाजित है, और 00:

11: 
10: 101 100 
01: 011 010 
00: 000 001 

अब, हम 00 तत्वों के साथ किसी भी 11 तत्वों युग्मित नहीं किया जा सकता है, तो हम सिर्फ 10 और 01 समूहों पर recurse। इसका मतलब यह है कि हम 100, 101, 010, और 011 समूहों का निर्माण: उन्हें में सिर्फ एक तत्व के साथ बाल्टी के लिए नीचे अब हम कर रहे हैं कि

101: 101 
100: 100 
011: 011 
010: 010 

, हम बस जोड़े जाँच कर सकते हैं 101 और 010 (जो 111 देता है) और 100 और 011 (जो 111 देता है)। या तो विकल्प यहां काम करता है, इसलिए हमें लगता है कि इष्टतम उत्तर 7 है।

आइए इस एल्गोरिदम के चलने वाले समय के बारे में सोचें। ध्यान दें कि अधिकतम रिकर्सन गहराई ओ (एलजी यू) है, क्योंकि संख्याओं में केवल ओ (लॉग यू) बिट्स हैं। पेड़ में प्रत्येक स्तर पर, प्रत्येक संख्या बिल्कुल एक रिकर्सिव कॉल में दिखाई देती है, और प्रत्येक रिकर्सिव कॉल 0 और 1 समूहों में संख्याओं की कुल संख्या के अनुपात में काम करती है, क्योंकि हमें उन्हें अपने बिट्स द्वारा वितरित करने की आवश्यकता होती है। नतीजतन, रिकर्सन पेड़ में ओ (लॉग यू) स्तर हैं, और प्रत्येक स्तर ओ (एन) काम करता है, जो ओ (एन लॉग यू) का कुल काम देता है।

आशा है कि इससे मदद मिलती है! यह एक भयानक समस्या थी!

Answer 2

साइन बिट को अनदेखा करते हुए, मानों में से एक उच्चतम महत्वपूर्ण बिट सेट वाले मानों में से एक होना चाहिए। जब तक सभी मानों में उस बिट सेट सेट नहीं होता है, तो इस मामले में आप अगले उच्चतम महत्वपूर्ण बिट पर जाते हैं जो सभी मानों में सेट नहीं होता है। तो आप एचएसबी को देख कर पहले मूल्य के लिए संभावनाओं को कम कर सकते हैं। उदाहरण के लिए, यदि संभावनाएं

0x100000 
0x100ABC 
0x001ABC 
0x000ABC 

अधिकतम जोड़ी का पहला मान या तो 0x100000 या 0x10ABCD होना चाहिए।

@ आंतरिक सर्वर त्रुटि मुझे नहीं लगता कि सबसे छोटा जरूरी है। मेरे पास दूसरे मूल्य को कम करने के लिए कोई अच्छा विचार नहीं है। संभवतः पहले मानों की सूची में कोई भी मान नहीं है। मेरे उदाहरण में, 0x001ABC या 0x000ABC।

Answer 3

एक पुनरावर्ती कार्य करें जो पूर्णांक, ए और बी की दो सूचियों को अपने तर्क के रूप में लेता है। इसके वापसी मूल्य के रूप में, यह दो पूर्णांक देता है, ए से एक और बी से एक, जो दोनों के एक्सओआर को अधिकतम करता है। यदि सभी पूर्णांक 0 हैं, तो वापसी (0,0)। अन्यथा, फ़ंक्शन कुछ प्रोसेसिंग करता है और खुद को बार-बार दो बार कॉल करता है, लेकिन छोटे पूर्णांक के साथ। रिकर्सिव कॉल में से एक में, यह सूची ए से एक पूर्णांक लेने के लिए 1 से बिट के लिए एक पूर्णांक लेता है, और दूसरी कॉल में यह सूची बी से एक पूर्णांक लेने के लिए 1 से बिट के लिए आपूर्ति करने पर विचार करता है।

मेरे पास विवरण भरने के लिए समय नहीं है, लेकिन हो सकता है कि यह उत्तर देखने के लिए पर्याप्त होगा? साथ ही, मुझे यकीन नहीं है कि रन टाइम एन^2 से बेहतर होगा, लेकिन शायद यह होगा।

Answer 4

एक बहुत ही रोचक समस्या!

• पहले द्विआधारी प्रतिनिधित्व का उपयोग करके सभी नंबरों से एक द्विआधारी पेड़ का निर्माण और उन्हें पेड़ में सॉर्ट सबसे महत्वपूर्ण बिट पहले (सबसे लंबे समय तक नंबर मिलान करने के लिए अग्रणी शून्य जोड़ने): यहाँ मेरी विचार है। रूट से प्रत्येक पथ को किसी भी पत्ते को मूल सेट से एक नंबर का प्रतिनिधित्व करता है।
• ए और बी को पेड़ नोड पर पॉइंटर्स दें और उन्हें रूट पर प्रारंभ करें।
• अब प्रत्येक चरण में विपरीत किनारों का उपयोग करने की कोशिश कर रहे पेड़ को नीचे और नीचे ले जाएं, यानी 0-किनारे के नीचे एक चाल, बी 1-एज तक नीचे चला जाता है जब तक कि यह संभव न हो।

यदि कोई और बी पत्ती तक पहुंचता है, तो उसे "बहुत कम" समान बिट्स के साथ दो संख्याओं को इंगित करना चाहिए।

मैंने अभी इस एल्गोरिदम को बनाया है और यह नहीं पता कि यह सही है या इसे कैसे साबित किया जाए। हालांकि यह ओ (एन) चलने का समय होना चाहिए।

Answer 5

हम प्रत्येक तत्व के साथ xor कर रहे सरणी के माध्यम से ओ (एन) समय में अधिकतम संख्या पा सकते हैं। मान लीजिए एक्सोर ऑपरेशन लागत ओ (1) है हम ओ (एन) समय में दो संख्याओं के अधिकतम xor पा सकते हैं।

Answer 6

इसे Trie का उपयोग करके समय जटिलता में हल किया जा सकता है।

• एक त्रिभुज का निर्माण। प्रत्येक पूर्णांक कुंजी के लिए, ट्राई का प्रत्येक नोड सबसे महत्वपूर्ण बिट से शुरू होने वाले प्रत्येक बिट (0 या 1) को पकड़ लेगा।
• अब arr[0, 1, ..... N]
  • से प्रत्येक arr[i] तत्व के लिए arr[i] के लिए अधिकतम संभव XOR मान प्राप्त करने के लिए क्वेरी को निष्पादित करें। हम विभिन्न प्रकार के बिट्स (0^1 या 1^0) के xor जानते हैं हमेशा 1 है। तो प्रत्येक बिट के लिए क्वेरी के दौरान, विपरीत बिट नोड को पार करने की कोशिश करें। यह उस विशेष बिट को 1 परिणामस्वरूप xor मान को अधिकतम करने में परिणाम देगा। यदि विपरीत बिट के साथ कोई नोड नहीं है, तो केवल उसी नोड को पार करें।
  • क्वेरी के बाद, arr[i] trie में डालें।
  • प्रत्येक तत्व के लिए, अधिकतम ज़ोर मान को ट्रैक रखें।
  • प्रत्येक नोड के माध्यम से चलने के दौरान, दूसरी कुंजी बनाएं जिसके लिए ज़ोर को अधिकतम किया जा रहा है।

N के लिए तत्वों, हम एक क्वेरी (O(logN)) और प्रत्येक तत्व के लिए एक प्रविष्टि (O(logN)) की जरूरत है। तो समग्र समय जटिलता O(NlogN) है।

आप in this thread पर काम करने के तरीके पर अच्छा चित्रमय स्पष्टीकरण पा सकते हैं।

const static int SIZE = 2; 
const static int MSB = 30; 
class trie { 
private: 
    struct trieNode { 
     trieNode* children[SIZE]; 
     trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       children[i] = nullptr; 
      } 
     } 
     ~trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       delete children[i]; 
       children[i] = nullptr; 
      } 
     } 
    }; 
    trieNode* root; 
public: 
    trie(): root(new trieNode()) { 
    } 
    ~trie() { 
     delete root; 
     root = nullptr; 
    } 

    void insert(int key) { 
     trieNode* pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(!pCrawl->children[bit]) { 
       pCrawl->children[bit] = new trieNode(); 
      } 
      pCrawl = pCrawl->children[bit]; 
     } 
    } 

    int query(int key, int& otherKey) { 
     int Xor = 0; 
     trieNode *pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(pCrawl->children[!bit]) { 
       pCrawl = pCrawl->children[!bit]; 
       Xor |= (1 << i); 
       if(!bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
      } else { 
       if(bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
       pCrawl = pCrawl->children[bit]; 
      } 
     } 
     return Xor; 
    } 
}; 

pair<int, int> findMaximumXorElements(vector<int>& arr) { 
    int n = arr.size(); 
    int maxXor = 0; 
    pair<int, int> result; 
    if(n < 2) return result; 
    trie* Trie = new trie(); 
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse 
    for(int i = 0; i < n; i++) { 
     int elem = 0; 
     int curr = Trie->query(arr[i], elem); 
     if(curr > maxXor) { 
      maxXor = curr; 
      result = {arr[i], elem}; 
     } 
     Trie->insert(arr[i]); 
    } 
    delete Trie; 
    return result; 
}