मान लीजिए कि हमारे पास संख्याओं का एक गैर-रिक्त सरणी है, a0, a1, a2,… , an-1, जहां 0 ≤ ai <231. हमें ai का अधिकतम परिणाम ज्ञात करना है एक्सओआर एजे, जहां 0 आई, जे <एन। तो अगर इनपुट [3,10,5,15,2,8] जैसा है, तो आउटपुट 28 होगा। अधिकतम परिणाम 5 XOR 25 =28 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
इंसर्टनोड () को परिभाषित करें, यह वैल और हेड लेगा
-
वक्र:=सिर
-
मेरे लिए 31 से 0 की सीमा में
-
बिट:=वैल / (2^i) और 1
-
अगर बच्चे [बिट] का कर्व शून्य है, तो बच्चे का [बिट] करंट:=नया नोड
-
curr :=बच्चे [बिट] करी के
-
-
खोज () विधि को परिभाषित करें। यह इनपुट के रूप में वैल और हेड लेगा
-
curr :=head, ans :=0
-
मेरे लिए 31 से 0 की सीमा में
-
बिट:=वैल / (2^i) और 1
-
यदि बच्चे [बिट] का कर्व शून्य है, तो उत्तर :=उत्तर या (2^1)/p>
-
curr :=बच्चे [बिट] करी के
-
-
वापसी उत्तर
-
मुख्य विधि से, निम्न कार्य करें -
-
उत्तर :=0
-
n :=अंकों का आकार
-
सिर :=नया नोड
-
मैं के लिए 0 से n -1 की सीमा में, insertNode(nums[i], head)
-
मैं के लिए 0 से n - 1 की सीमा में, उत्तर:=अधिकतम उत्तर और खोजें (अंक [i], शीर्ष)
-
वापसी उत्तर
उदाहरण (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