Java simple greedy + bit manipulation solution, O(n) time, with explanation (without HashMap)


  • 3
    Z

    Hi there! I am posting my recursive solution based on bit manipulation. The idea is strightforward. Let us think about the resultant number. Well, it is clear that, in order to, maximize the resultant number, we have to maximize the number of set bits with higher order. In other words, starting from the left most possible bit position we check if there is a pair of numbers, such that their bits in the current position will XOR'ed up to 1. Obviously there are only two options to satisfy that condition 1,0 or 0,1 for each bit position. Thus, we always divide the numbers into two parts, those that has set bits in current position and those that has zero bits in current position. Consequently if we can divide the numbers in such a way, it means we can obtain set bit by some combination in the current position. Otherwise, we decrease factor of two ( bit position) while we can't divide the numbers and we didn't reach the last bit position. For example

                           {1,2,3} <- bit position 1
                            /    \
                        {1}      {2, 3} <- bit position 0
                        / \        /  \
                      X   {1}   {2}   {3}    
    

    In the example above, given array {1,2,3} we can start from bit position 1, because it is the highest bit order in current array. Then we divide it according to the values of current bit. Correspondingly {1} has 0 bit in position 1, whereas 2 and 3 have set bits. It means our resultant number has set bit in position 1. Next we divide the halves into halves similarly for bit position 0. Here you can see that array {1} does not have numbers which bits in position 0 are not set, but has a number which has set bit in that position({1}). In turn the right part is divided to {2} and {3} correspondingly, because 2 has 0 bit in 0th position and 3 has set bit in 0th position. That fact means that, we can also XOR 1 with 2 and get set bit in position 1, therefore the answer is 3 = 2^1+2^0;
    Actually the running time of the algorithm isO(n*h) where h is the height of the tree, but according to the problem statement h is constant(32, only integers). Because of that fact the algorithm may be considered as linear.

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            int max = 0;
            if(nums == null || nums.length == 0) return 0;
            List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
            
            for(int i = 0;i<nums.length;i++){
                max= Math.max(max, nums[i]);
            }
            int p = 31;
            while(p>0 && (max & (1<<p)) == 0) p--;
            int fact = 0;
            while(p>=0 && (left.isEmpty() || right.isEmpty())){
                fact = 1<<p;
                for(int i = 0;i<nums.length;i++){
                    if((nums[i] & fact) == 0){
                        left.add(nums[i]);
                    } else {
                        right.add(nums[i]);
                    }
                }
                p--;
            }
            if(left.isEmpty() || right.isEmpty()) fact = 0;
            // System.out.println(fact);
            return fact+maxXOR(p, left, right);
        }
        
        public int maxXOR(int p, List<Integer> left, List<Integer> right){
            if(p<0) return 0;
            // int fact;
            List<Integer> leftZero  = new ArrayList<>(), rightZero  = new ArrayList<>();
            List<Integer> leftOne = new ArrayList<>(), rightOne = new ArrayList<>();
            int fact = 1<<p;
            
            while(p>=0 && ((leftZero.isEmpty() || rightOne.isEmpty()) && (leftOne.isEmpty() || rightZero.isEmpty()))){
                fact = 1<<p;
                leftZero.clear();
                leftOne.clear();
                rightZero.clear();
                rightOne.clear();
                fill(fact, left, leftZero, leftOne);
                fill(fact, right, rightZero, rightOne);
                p--;
            }
            if(((leftZero.isEmpty() || rightOne.isEmpty()) && (leftOne.isEmpty() || rightZero.isEmpty()))) {
                return 0;
            }
            // System.out.println("+"+fact);
            return fact+Math.max(maxXOR(p, leftZero, rightOne), maxXOR(p, rightZero, leftOne)); 
        }
        
        public void fill(int fact, List<Integer> list, List<Integer> zero, List<Integer> one){
            for(Integer num:list){
                if((fact & num) == 0) {
                    zero.add(num);
                } else {
                    one.add(num);
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.