📌[ Java] A very detailed explanation with sim. understanding | Trie + Bit
*\nPlease upvote if the explanation helps, as it keeps up the motivation to provide such posts. \n\nPS : This must be a Hard Problem.\n\nExplanation Flow : \n G
****\nPlease upvote if the explanation helps, as it keeps up the motivation to provide such posts. \n****\nPS : This must be a Hard Problem.\n\n**Explanation Flow :** \n* Given statements/Observations\n* Simulation of logic\n* Approach\n* Code\n* Bit Logic \n\n**\u2714\uFE0F Given statements:** \n\nGiven an integer array `nums`, \nreturn the maximum result of `nums[i]` XOR `nums[j]`, where `0 <= i <= j < n.`\n\n**Let\'s first solve a smaller version of this problem:** \n\nGiven an array `nums` and a no `x`, find the maximum result of `nums[i]` XOR `x`.\nWe can generalise the outcome from this to solve our main problem.\n`nums : [ 4, 5, 8, 9 ]`\n`x` : `6`\n\nLet\'s create a trie from `nums`.\nIn order to get a maximum number after xor, we want to have our bits set from `MSB` because of powers of 2 are high. Let me take an example : \n\n![image](https://assets.leetcode.com/users/images/3852e0c2-ebed-415c-8118-904c56a8724b_1643251059.2812488.png)\n\n****\n\nSo,  our code flow will be something like this : [ Simulation ]\nSee how we have removing those inputs which does not help us reach the maximum result ! This is achieved by Trie, we keep moving in the correct direction hence, removing the invalid inputs from the way.\n\n****\nIf the simulation is bit too fast, here is the link of files :\nhttps://drive.google.com/drive/folders/1VeNW7_jFif6-czvbsgEZFxiOSOCeQb3b?usp=sharing\n\n\n![image](https://assets.leetcode.com/users/images/5bbde8f6-016e-4987-9ea8-2b51021b8e03_1643256352.788602.gif)\n\n\n****\n\nWe have to perform this action for every `A[i]` and get the maximum.\n\n**\u2714\uFE0F Approach :** \n\n1. We insert A[i] in Binary Trie, starting from `MSB` to `LSB`.\n2. Each A[i] will be stored in `1` and `0` corresponding to its bit position.\n3. For every element `A[i]`, we check what is the current maximum result we could get from xor ( refer simulation )\n4. Get overall maximum\n\n**\u2714\uFE0F Code :** \n\n```\nclass Node {\n    HashMap<Integer, Node> children;\n    Node() {\n        this.children = new HashMap<>();\n    }\n}\n\nclass Trie {\n    Node root;\n    \n    Trie() {\n        this.root = new Node();\n    }\n    \n    public void insert(int[] A) {\n        for(int num : A) {\n            Node curr = this.root;\n            for(int i=31;i>=0;i--) {\n                int currBit = (num >> i) & 1;\n                if(!curr.children.containsKey(currBit)) \n                    curr.children.put(currBit, new Node());\n                curr = curr.children.get(currBit);\n            }\n        }\n    }\n}\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n        Trie trie = new Trie();\n        trie.insert(nums);\n        \n        int max = 0;\n\n        for(int num : nums) {\n            Node curr = trie.root;\n            int currSum = 0;\n            for(int i=31;i>=0;i--) {\n                int requiredBit = 1-((num >> i) & 1); // if A[i] is 0, we need 1 and if A[i] is 1, we need 0. Thus, 1 - A[i]\n                if(curr.children.containsKey(requiredBit)) {\n                    currSum |= (1<<i); // set ith bit of curr result\n                    curr = curr.children.get(requiredBit);\n                } else {\n                    curr = curr.children.get(1-requiredBit);\n                }\n            }\n            max = Math.max(max, currSum); // get max number\n        }\n        return max;\n    }\n}\n\n```\n\n\n**\u2714\uFE0F Complexity Analysis** : \n* TC : `O(n * 32)` + `O(n)` = `O(n)`\n* SC : `O(2^h - 1)` == `O(2^32 - 1)` == `O(1)` [ refer @kazuwuqt comment below ]\n\n**Bit Logic :**\n\nShift operators are used to shift the bits of a number left or right, i.e. multiplying or dividing the number by two, respectively.\n**Syntax : "num" "op" "positions_to_shift"**\n\n`>>` is a right shift operator. There are two ways to think about it : \n1. It shift the number by *positions* specified to the right. ( fill unoccupied positions with 0 ) or,\n2. It divides the number by 2^positions\n\nby doing `num >> i` , **main aim is to get the ith bit of number.**\nI am shifting the num by `i` positions ( we get decimal number ) and getting the bit at that position ( by doing `& 1` -> 1&0 = 0 and 1&1 = 1 ).\n\nFor eg : \n`num = 5 ( 0 1 0 1 )`\nnum >> `2` means \n1. shifting the num by 2 position -> 0 0 1 0 -> 0 0 0 1 i.e. 1 ( in decimal )  `& 1`  yields `1` i.e. the 2nd bit of number 5 is `1` \n2. divide num by 2^`2` ->  5/4 -> 1 `& 1` yields `1` i.e. the 2nd bit of number 5 is `1` .\n\n****\nIf there is any suggestion, pls let me know\n****
['Bit Manipulation', 'Trie', 'Java']