Tìm XOR tối đa của số nguyên đã cho trong một dòng số nguyên trong C ++

Trong bài toán này, chúng tôi nhận được Q truy vấn, mỗi truy vấn là một trong các loại sau,

Loại 1 - insert (1, i) để thêm phần tử có giá trị i, trong cấu trúc dữ liệu của bạn.

Loại 2 - findXOR (2, i), để tìm XOR của tất cả các phần tử của cấu trúc dữ liệu với phần tử i.

Cấu trúc dữ liệu chỉ nên chứa 1 phần tử ban đầu sẽ là 0.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)

Đầu ra

15 15

Giải thích

Solving each query,
(1, 9) => data structure => {9}
(1, 3) => data structure => {9, 3}
(1, 7) => data structure => {9, 3, 7}
(2, 8) => maximum XOR(_, 8) = 15, XOR(7, 8)
(1, 5) => data structure => {9, 3, 7, 5}
(2, 12) => maximum XOR(_, 12) = 15, XOR(3, 12)

Phương pháp tiếp cận giải pháp

Giải pháp cho vấn đề này có thể được tìm thấy bằng cách sử dụng cấu trúc dữ liệu trie, là một loại cây tìm kiếm đặc biệt. Chúng ta sẽ sử dụng một bộ ba trong đó mỗi nút có hai nút con để lưu trữ các giá trị nhị phân của một số. Sau đó, chúng tôi sẽ thêm giá trị nhị phân của số vào trie cho mỗi truy vấn loại 1. Đối với truy vấn loại 2, chúng tôi sẽ tìm đường dẫn trong trie cho giá trị đã cho và sau đó số lượng cấp sẽ cho kết quả.

Để biết thêm về cấu trúc dữ liệu trie, hãy truy cập trie.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include<bits/stdc++.h>
using namespace std;
struct Trie {
   Trie* children[2];
   bool isLeaf;
};
bool check(int N, int i) {
   return (bool)(N & (1<<i));
}
Trie* newNode() {
   Trie* temp = new Trie;
   temp->isLeaf = false;
   temp->children[0] = NULL;
   temp->children[1] = NULL;
   return temp;
}
void insertVal(Trie* root, int x) {
   Trie* val = root;
   for (int i = 31; i >= 0; i--) {
      int f = check(x, i);
      if (! val->children[f])
         val->children[f] = newNode();
         val = val->children[f];
   }
   val->isLeaf = true;
}
int solveQueryType2(Trie *root, int x){
   Trie* val = root;
   int ans = 0;
   for (int i = 31; i >= 0; i--) {
      int f = check(x, i);
      if ((val->children[f ^ 1])){
         ans = ans + (1 << i);
         val = val->children[f ^ 1];
      }
      else
      val = val->children[f];
   }
   return ans;
}
void solveQueryType1(Trie *root, int x){
   insertVal(root, x);
}
int main(){
   int Q = 6;
   int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
   Trie* root = newNode();
   for(int i = 0; i < Q; i++){
      if(query[i][0] == 1 ){
         solveQueryType1(root, query[i][1]);
         cout<<"Value inserted to the data Structure. value =
         "<<query[i][1]<<endl;
      }
      if(query[i][0] == 2){
         cout<<"The maximum XOR with "<<query[i][1]<<" is
         "<<solveQueryType2(root, query[i][1])<<endl;
      }
   }
   return 0;
}

Đầu ra

Value inserted to the data Structure. value = 9
Value inserted to the data Structure. value = 3
Value inserted to the data Structure. value = 7
The maximum XOR with 8 is 15
Value inserted to the data Structure. value = 5
The maximum XOR with 12 is 15