C++ এ একটি অ্যারেতে দুটি সংখ্যার সর্বোচ্চ XOR

ধরুন আমাদের কাছে সংখ্যার একটি অ-খালি অ্যারে আছে, 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