fork download 
  1. #include<iostream>
  2. #include<math.h>
  3. #include<climits>
  4. using namespace std;
  5. class trienode{
  6. public:
  7.     trienode *left;//store 0
  8.     trienode *right;//store 1
  9. };
  10. void Insert(int element, trienode *root){
  11.     trienode *curr = root;
  12.     for(int i=0;i<32;i++){
  13.         //find the current bit(1 or 0)
  14.         int bit = (element>>i) & 1;
  15.         if(bit == 0){
  16.             if(curr->left == NULL){
  17.                 //make left child
  18.                 curr->left = new trienode();
  19.             }
  20.             curr = curr->left;
  21.         }
  22.         else{
  23.             if(curr->right == NULL){
  24.                 //make right child
  25.                 curr->right = new trienode();
  26.             }
  27.             curr = curr->right;
  28.         }
  29.     }
  30. }
  31.  
  32. int findMaxXorPair(trienode *root, int arr[] ,int n, int ele){
  33.     int max_xor = INT_MIN;
  34.     trienode *curr = root;
  35.     int value = ele;
  36.     int curr_xor = 0;
  37.     for(int j=0;j<32;j++){
  38.         int b = (value >> j) & 1;
  39.         if(b == 0){
  40.             //current bit is 0 and searching fr 1 for max xor value
  41.             if(curr->right != NULL){
  42.                 curr = curr->right;
  43.                 curr_xor += (int)pow(2,j);
  44.             }
  45.             else{
  46.                 curr = curr->left;
  47.             }
  48.         }
  49.         else{
  50.             //current bit is 1 and searching fr 0 for max xor value
  51.             if(curr->left != NULL){
  52.                 curr = curr->left;
  53.                 curr_xor += (int)pow(2,j);
  54.             }
  55.             else{
  56.                 curr = curr->right;
  57.             }
  58.         }
  59.     }
  60.     if(curr_xor>max_xor){
  61.         max_xor = curr_xor;
  62.     }
  63.     return max_xor;
  64. }
  65.  
  66. int main(){
  67.     int n;
  68.     cin>>n;
  69.     int arr[n];
  70.     for(int i = 0;i < n;i++){
  71.         cin>>arr[i];
  72.     }
  73.     trienode *root = new trienode();
  74.     int result = INT_MIN;
  75.     for(int i=0;i<n;i++){
  76.         Insert(arr[i],root);
  77.         int x = findMaxXorPair(root,arr,n,arr[i]);
  78.         if(x>result){
  79.             result = x;
  80.         }
  81.  
  82.     }
  83.     cout<<result<<endl;
  84. return 0;}
  85.  
Success #stdin #stdout 0s 4464KB
comments (?)
stdin 
6
3 10 5 25 2 8
stdout 
19
https://ideone.com/pd4efr
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!