🔥✅ | Beats 92.95% | ✅  Tries | ✅ O(N*32) | ✅🔥
\n# Intuition\nThe goal is to find the maximum XOR of two numbers in an array. To efficiently solve this, we can use a Trie (prefix tree) data structure, which 
![Screenshot from 2024-06-15 22-20-44.png](https://assets.leetcode.com/users/images/415e6513-855a-4608-b96c-37676c259b56_1718470261.295846.png)\n# Intuition\nThe goal is to find the maximum XOR of two numbers in an array. To efficiently solve this, we can use a Trie (prefix tree) data structure, which allows us to store binary representations of the numbers and perform efficient lookups to maximize the XOR results.\n\n# Approach\n1. Trie Structure:\n\n    - We define a Node class to represent each node in the Trie, where each node has two potential links (0 and 1).\n    - The Tries class contains methods to insert a number in its binary form into the Trie and to find the maximum XOR for a given number.\n2. Insertion:\n    - For each number, insert its 32-bit binary representation into the Trie.\n3. Maximizing XOR:\n\n    - For each number, traverse the Trie to find the number that would produce the maximum XOR with the current number.     This is done by trying to take the opposite bit (1-bit) at each step if possible.\n4. Finding the Maximum XOR:\n\n    - As we insert each number into the Trie, we simultaneously check for the maximum XOR possible with the numbers already inserted.\n# Complexity\n- Time Complexity: Insertion and query operations for each number take O(32) time because we are dealing with 32-bit integers. Hence, for n numbers, the total time complexity is O(n * 32) = O(n).\n- Space Complexity:\nThe space complexity is O(n * 32) = O(n), where n is the number of integers, because each node might have up to 32 levels.\n# Code\n```C++ []\nstruct Node {\n    Node * links[2];\n    bool isSet(int bit){\n        return (links[bit] != NULL);\n    }\n    Node* get(int bit){\n        return links[bit];\n    }\n    void put(int bit,Node * node){\n        links[bit] = node;\n    }\n};\n\nclass Tries{\nprivate:\n    Node * root;\npublic:\n    Tries(){\n        root = new Node();\n    }\n    void insert(int num){\n        Node * node = root;\n        for(int i=31; i>=0; i--){\n            int bit = (num >> i) & 1;\n            if(!node->isSet(bit)){\n                node->put(bit,new Node());\n            }\n            node = node->get(bit);\n        }\n    }\n    int getMax(int num){\n        Node * node = root;\n        int maxi=0;\n        for(int i=31; i>=0; i--){\n            int bit = (num >> i) & 1;\n            if(node->isSet(1-bit)){\n                maxi |= (1<<i);\n                node = node->get(1-bit);\n            }else{\n                node=node->get(bit);\n            }\n\n        }\n        return maxi;\n    }\n};\n\nclass Solution {\npublic:\n    int findMaximumXOR(vector<int>& nums) {\n        Tries* trie = new Tries();\n        int n=nums.size(),res=0;\n        for(int i=n-1; i>=0; i--){\n            trie->insert(nums[i]);\n            res = max(res,trie->getMax(nums[i]));         \n        }\n        return res;\n    }\n};\n```\n```Java []\nclass Node {\n    Node[] links = new Node[2];\n\n    boolean isSet(int bit) {\n        return links[bit] != null;\n    }\n\n    Node get(int bit) {\n        return links[bit];\n    }\n\n    void put(int bit, Node node) {\n        links[bit] = node;\n    }\n}\n\nclass Tries {\n    private Node root;\n\n    public Tries() {\n        root = new Node();\n    }\n\n    public void insert(int num) {\n        Node node = root;\n        for (int i = 31; i >= 0; i--) {\n            int bit = (num >> i) & 1;\n            if (!node.isSet(bit)) {\n                node.put(bit, new Node());\n            }\n            node = node.get(bit);\n        }\n    }\n\n    public int getMax(int num) {\n        Node node = root;\n        int maxi = 0;\n        for (int i = 31; i >= 0; i--) {\n            int bit = (num >> i) & 1;\n            if (node.isSet(1 - bit)) {\n                maxi |= (1 << i);\n                node = node.get(1 - bit);\n            } else {\n                node = node.get(bit);\n            }\n        }\n        return maxi;\n    }\n}\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n        Tries trie = new Tries();\n        int res = 0;\n        for (int i = nums.length - 1; i >= 0; i--) {\n            trie.insert(nums[i]);\n            res = Math.max(res, trie.getMax(nums[i]));\n        }\n        return res;\n    }\n}\n```\n\n![](https://mir-s3-cdn-cf.behance.net/project_modules/1400/e0bcc865344605.5f62f95707bd4.jpg)
['Array', 'Bit Manipulation', 'Trie', 'C++', 'Java']