ধরুন আমাদের কাছে সংখ্যার একটি অ-খালি অ্যারে আছে, a0, a1, a2, … , an-1, যেখানে 0 ≤ ai <231। আমাদের ai-এর সর্বোচ্চ ফলাফল খুঁজে বের করতে হবে XOR aj, যেখানে 0 ≤ i, j
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
insertNode() সংজ্ঞায়িত করুন, এটি ভ্যাল এবং হেড লাগবে
-
curr :=মাথা
-
আমি 31 থেকে 0
রেঞ্জের জন্য-
bit :=val / (2^i) এবং 1
-
যদি curr এর চাইল্ড[বিট] নাল হয়, তাহলে curr এর চাইল্ড[বিট] :=নতুন নোড
-
curr :=curr এর শিশু[বিট]
-
-
find() পদ্ধতি সংজ্ঞায়িত করুন। এটি ইনপুট হিসাবে ভ্যাল এবং হেড গ্রহণ করবে
-
curr :=মাথা, উত্তর :=0
-
আমি 31 থেকে 0
রেঞ্জের জন্য-
bit :=val / (2^i) এবং 1
-
যদি curr এর চাইল্ড[বিট] শূন্য হয়, তাহলে ans :=ans OR (2^1)/p>
-
curr :=curr এর শিশু[বিট]
-
-
উত্তর ফেরত দিন
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
উত্তর :=0
-
n :=সংখ্যার আকার
-
head :=নতুন নোড
-
0 থেকে n – 1 রেঞ্জের i জন্য, insertNode(nums[i], head)
-
0 থেকে n – 1 পরিসরে i এর জন্য, উত্তর :=উত্তরের সর্বোচ্চ এবং খুঁজুন (সংখ্যা[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