XOR tối đa của hai số trong một mảng trong C ++

Giả sử chúng ta có một mảng số không rỗng, a0, a1, a2,…, an-1, trong đó 0 ≤ ai <231. Chúng ta phải tìm kết quả lớn nhất của ai XOR aj, trong đó 0 ≤ i, j

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định insertNode (), điều này sẽ lấy val và head

• curr:=đầu

• cho tôi trong phạm vi 31 đến 0

  • bit:=val / (2 ^ i) VÀ 1

  • nếu con [bit] của curr là null, thì con [bit] của curr:=nút mới

  • curr:=child [bit] of curr

• Định nghĩa phương thức find (). Điều này sẽ lấy val và head làm đầu vào

• curr:=head, ans:=0

• cho tôi trong phạm vi 31 đến 0

  • bit:=val / (2 ^ i) VÀ 1

  • nếu con [bit] của curr là null, thì ans:=ans OR (2 ^ 1) / p>

  • curr:=child [bit] of curr

• trả lại ans

• Từ phương thức chính, thực hiện như sau -

• ans:=0

• n:=kích thước của nums

• head:=nút mới

• đối với tôi trong phạm vi từ 0 đến n - 1, insertNode (nums [i], head)

• đối với tôi trong phạm vi 0 đến n - 1, ans:=max of ans and find (nums [i], head)

• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

28