nikunjsoni

421

Jun 26th, 2021
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Trie{
  2. public:
  3.     Trie* children[2] = {};
  4.     bool leaf;
  5.     Trie(){
  6.         leaf = false;
  7.     }
  8. };
  9.  
  10. class Solution {
  11. private:
  12.     Trie* root = new Trie();
  13.  
  14. public:
  15.     void buildTree(vector<int> & nums){
  16.         for(int num : nums){
  17.             Trie* node = root;
  18.             for(int i = 31; i >= 0; i--){
  19.                 int bitOp = (num >> i) & 1;
  20.                 if(!node->children[bitOp]){
  21.                     node->children[bitOp] = new Trie();
  22.                 }
  23.                 node = node->children[bitOp];
  24.             }
  25.             node->leaf = true;
  26.         }
  27.     }
  28.    
  29.     int findMaximumXOR(vector<int>& nums) {
  30.         buildTree(nums);
  31.         int maxRes = 0, res = 0;
  32.         for(int i = 0; i < nums.size(); i++){
  33.             int num = nums[i];
  34.             Trie* node = root;
  35.             int index;
  36.             int res = 0;
  37.             for(int k = 31; k >= 0; k--){
  38.                 int bitOp = (num >> k) & 1;
  39.                 index = bitOp ? 0:1;
  40.                 if(node -> children[index]){
  41.                     res = (res<<1) | 1;
  42.                     node = node->children[index];
  43.                 }
  44.                 else{
  45.                     res <<= 1;
  46.                     node = node->children[index ? 0 : 1];
  47.                 }
  48.             }
  49.             maxRes = max(maxRes, res);
  50.         }
  51.         return maxRes;
  52.     }
  53. };
RAW Paste Data