# Java, bit manipulation and divide into two groups.

• ``````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);
}

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);
}

for(int num: notOne){
if(((num>>highBit) & 1) != 0) l01.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!

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