421_findMaximumXOR.java

//REF: https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap/8

// example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
// Since the MSB is 3, I'll start from i = 3 to make it simplify.

// i = 3, set = {1000, 0000}, max = 1000
// i = 2, set = {1100, 1000, 0100, 0000}, max = 1100
// i = 1, set = {1110, 1010, 0110, 0010}, max = 1100
// i = 0, set = {1110, 1011, 0111, 0010}, max = 1100

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        int mask = 0;
        for(int i = 31; i >= 0; i--){
            mask = mask | (1 << i);
            HashSet<Integer> set = new HashSet<Integer>();
            for(int n: nums){
                set.add(n & mask); // reserve Left bits and ignore Right bits
            }
            /* Use 0 to keep the bit, 1 to find XOR
             * 0 ^ 0 = 0 
             * 0 ^ 1 = 1
             * 1 ^ 0 = 1
             * 1 ^ 1 = 0
             */
            int tmp 
            int temp = max | (1 << i);// in each iteration, there are pair(s) whoes Left bits can XOR to max
            for(int prefix: set){
                if(set.contains(prefix ^ temp)){
                    max = temp;
                }
            }
        }
        return max;
    }
}