paradox64ce

XOR

Aug 12th, 2021
723
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class TrieNode{
  2.     public:
  3.     unordered_map<int, TrieNode*> children;
  4.     TrieNode(){
  5.         children = unordered_map<int, TrieNode*>();
  6.     }
  7. };
  8.  
  9. class Trie{
  10.   public:
  11.     TrieNode* root;
  12.    
  13.     Trie(){
  14.         root = new TrieNode();
  15.     }
  16.    
  17.     void insert(int x){
  18.         TrieNode* cur = root;
  19.         for(int j=30;j>=0;j--){
  20.             int v =  ((x)&(1<<j)!=0);
  21.             if(cur->children.find(v)==cur->children.end()){
  22.                 cur->children[v] = new TrieNode();
  23.             }
  24.             cur = cur->children[v];
  25.         }
  26.     }
  27.    
  28.     int maxXOR(int x){
  29.         TrieNode* cur = root;
  30.         int ans = 0;
  31.         for(int j = 30; j >= 0; j--){
  32.             if((x & (1<<j))!=0){
  33.                 if(cur->children.find(0)!=cur->children.end())
  34.                 {
  35.                     ans += (1<<j);
  36.                     cur = cur->children[0];
  37.                     // cout<<"0A";
  38.                 }
  39.                 else
  40.                 {
  41.                     // ans += (1<<j);
  42.                     cur = cur->children[1];
  43.                     // cout<<"1A";
  44.                 }
  45.             }
  46.             else
  47.             {
  48.                 if(cur->children.find(1)!=cur->children.end())
  49.                 {
  50.                     ans += (1<<j);
  51.                     cur = cur->children[1];
  52.                     // cout<<"1B";
  53.                 }
  54.                 else
  55.                 {
  56.                     // ans += (1<<j);
  57.                     cur = cur->children[0];
  58.                     // cout<<"0B";
  59.                 }
  60.             }
  61.         }
  62.         // cout<<"\n";
  63.         return ans;
  64.     }
  65. };
  66.  
  67. class Solution {
  68.    
  69. public:
  70.     int findMaximumXOR(vector<int>& nums){
  71.         int ans = 0;
  72.         Trie trie;
  73.         for(auto x : nums){
  74.             trie.insert(x);
  75.             ans = max(ans, trie.maxXOR(x));
  76.             // cout << x << " " << ans <<"\n";
  77.         }
  78.         return ans;
  79.     }
  80. };
RAW Paste Data