C++ में सरणी में दो संख्याओं का अधिकतम XOR

मान लीजिए हमारे पास संख्याओं की एक गैर-खाली सरणी है, a0, a1, a2, … , an-1, जहां 0 ≤ ai < 2^31। हमें ai XOR aj का अधिकतम परिणाम ढूंढना है, जहां 0 ≤ i, j < n।

उदाहरण के लिए, यदि इनपुट [3,10,5,25,2,8] जैसा है, तो आउटपुट 28 होगा। अधिकतम परिणाम 5 XOR 25 = 28 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• insertNode() परिभाषित करें, यह val और head लेगा
• curr := head
• i को 31 से 0 तक लूप करें
  • bit := val / (2^i) AND 1
  • यदि curr का child[bit] शून्य है, तो curr का child[bit] := नया नोड
  • curr := curr का child[bit]
• find() विधि परिभाषित करें। यह इनपुट के रूप में val और head लेगा
• curr := head, ans := 0
• i को 31 से 0 तक लूप करें
  • bit := val / (2^i) AND 1
  • यदि curr का child[!bit] शून्य है, तो ans := ans OR (2^i)
  • curr := curr का child[!bit]
  • अन्यथा curr := curr का child[bit]
• ans लौटाएं
• मुख्य विधि से, निम्नलिखित करें:
  • ans := 0
  • n := nums का आकार
  • head := नया नोड
  • i को 0 से n - 1 तक लूप करें, insertNode(nums[i], head)
  • i को 0 से n - 1 तक लूप करें, ans := ans और find(nums[i], head) का अधिकतम
  • ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; struct Node{    Node* child[2];    Node(){       child[1] = child[0] = NULL;    } }; class Solution {    public:    void insertNode(int val, Node* head){       Node* curr = head;       for(int i = 31; i>= 0; i--){          int bit = (val >> i) & 1;          if(!curr->child[bit]){             curr->child[bit] = new Node();          }          curr = curr->child[bit];       }    }    int find(int val, Node* head){       Node* curr = head;       int ans = 0;       for(int i = 31; i>= 0; i--){          int bit = (val >> i) & 1;          if(curr->child[!bit]){             ans |= (1 << i);             curr = curr->child[!bit];          } else {             curr = curr->child[bit];          }       }       return ans;    }    int findMaximumXOR(vector<int>& nums) {       int ans = 0;       int n = nums.size();       Node* head = new Node();       for(int i = 0; i < n; i++){          insertNode(nums[i], head);       }       for(int i = 0; i < n; i++){          ans = max(ans, find(nums[i], head));       }       return ans;    } }; main(){    vector<int> v = {3,10,5,25,2,8};    Solution ob;    cout << (ob.findMaximumXOR(v)); }

इनपुट

[3,10,5,25,2,8]

आउटपुट

28