Java, bit manipulation and divide into two groups.


  • 2
    N
    public class Solution {
        public int findMaximumXOR(int[] nums) {
           int max = Integer.MIN_VALUE;
           int highBit = 0, count = 0;
           for(int num: nums) max = Math.max(max, num);
           while(count<=31){
               if((max & (1<<count)) != 0) highBit = count;
               count++;
           }
           List<Integer> isOne = new ArrayList<>();
           List<Integer> notOne = new ArrayList<>();
           
           for(int num: nums){
               if(((num>>highBit) & 1) == 1) isOne.add(num);
               else notOne.add(num);
           }
           
           return recur(isOne, notOne, highBit-1);
        }
        private int recur(List<Integer> isOne, List<Integer> notOne, int highBit){
            if(isOne.size()==1 && notOne.size()==1) return isOne.get(0) ^ notOne.get(0);
            
            List<Integer> l11 = new ArrayList<>();
            List<Integer> l10 = new ArrayList<>();
            List<Integer> l01 = new ArrayList<>();
            List<Integer> l00 = new ArrayList<>();
            
            for(int num: isOne){
                if(((num>>highBit) & 1) != 0) l11.add(num);
                else l10.add(num);
            }
            
            for(int num: notOne){
                if(((num>>highBit) & 1) != 0) l01.add(num);
                else l00.add(num);
            }
            
            int max = 0;
            if(l11.size()!=0 && l00.size()!=0) max = recur(l11, l00, highBit-1);
            if(l10.size()!=0 && l01.size()!=0) max = Math.max(max, recur(l10,l01,highBit-1));
            return max;
        }
    }
    
    

    Time: O(nlog(HighestBit))

    Welcome any improvement suggestion and welcome to find bugs.

    Thanks!


Log in to reply
 

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