[JAVA] O(N) Time | Explained | Greedy Approach
Given a array of integers find the maximum xor..\n1. Do xor of each element with another and update the max value as and when you find a value.\n2. In the end r
Given a array of integers find the maximum xor..\n1. Do xor of each element with another and update the max value as and when you find a value.\n2. In the end return it.\n\nint ans = 0;\n\tfor(int n:nums){\n\tfor(int n1:nums){\n\t\tans = Math.max(ans, n^n1);\n\t}\n\t}\n\treturn ans;\n\t\n\nOR ---------------\n\t\n```import java.util.*;\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n        \n        int mask = 0, ans = 0, greedyPossibility = 0;\n        Set<Integer> set;\n        for(int i=31;i>-1;i--){\n                mask = mask |  1<< i ;\n\t\t\t\t\n                set = new HashSet<>();\n                for(int n:nums)\n                    set.add(mask & n);\n            \n                greedyPossibility = ans | (1 << i);\n\t\t\t\t\n         //\n            Iterator<Integer> it = set.iterator();\n               while(it.hasNext()){\n                    if(set.contains(greedyPossibility^it.next())){\n                        ans = greedyPossibility;\n                        break;\n                    }\n                }\n        }\n        return ans;\n        \n    }\n}\n```\n\nWhat we are doing here is GREEDY approach.\n\nWe want XOR to be as large as possible...  i.e. so we\'ll try to find a pair in the numbers whose XOR creates a large number. \nAs we know,\n10000 > 01111 (i.e. for same number of bits in a number, if we could find a XOR of pairs such that XOR creates 1 as MSB, not caring about its other bits, then we are good to go with this number. (i.e. the XOR of the  prefix of 2 numbers if gives 1, then we choose it.)\nBasically,\nSo if a pair let\'s say 10000 and 11111 gives XOR=> 01111 and\nanother let\'s say      01111 and 11111 gives XOR -> 10000 ... so here we choose this pair.\n\n\ni.e we only care if we are able to get XOR of 2 numbers where MSB is 1. If we find it, we have a large number. And so on we\'ll try to do for next bits starting from left to right.\n\nPrefix means the starting part of a number/word. Hence, first we only get the prefix of all numbers. By masking with a number like 10000.\nIf prefixes of 2 number prefixes gives us 1 (followed by zeroes or any bits), we take it and this is our answer.\n\nIteration 1\nSay, we get numbers prefixes in the set as {0000,1000} i.e. the possibility of all kinds of prefixes (most significant bit, single bit)  from nums array.\nSo the greedyPossibility is = 0 | 1<<4 i.e 1000 (this is what we want).\nIf any 2 number prefixes gives greedyPossibility. Then we are sure answer will have 4th bit as 1. Hence ans = 1000 for now.\n\nIteration 2\nSay, we get number prefixes( now 2 most signifcant bits), as. {0000,1100,0100,1000), now we know ans is 1000 i.e. our 4th bit can be one.. but can we get 3rd bit also one i.e. can greedyPossibility be 1000 | 1<<3 i.e. 1100.\nIf any 2 number prefixes gives greedyPossibility, Then we are sure answer will have 3rd bit as 1. Hence ans =greedyPossibility = 1100 for now.\n\nIteration 3\nSay , we get number prefixes(now 3 most signifcant bits) of all numbers as {0000, 1110, 1100, 0010, 0100}, now we know ans is 1100 i.e. our 4th and 3rd bit are 1, but can we have 2nd bit also one i.e. can answer be =ans | 1<<2 i.e. 1110. \nIf any 2 number prefixes (from set) gives greedyPossibility, then we are sure answer will have 2nd bit as 1. If not then our 2nd bit stays 0. And our answer for now is 1100.\n\nand so on.\n
[]