public class Solution {
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for(int i = 31; i >= 0; i){
mask = mask  (1 << i);
Set<Integer> set = new HashSet<>();
for(int num : nums){
set.add(num & mask);
}
int tmp = max  (1 << i);
for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
}
Java O(n) solution using bit manipulation and HashMap



This algorithm's idea is:
to iteratively determine what would be each bit of the final result from left to right. And it narrows down the candidate group iteration by iteration. e.g. assume input are a,b,c,d,...z, 26 integers in total. In first iteration, if you found that a, d, e, h, u differs on the MSB(most significant bit), so you are sure your final result's MSB is set. Now in second iteration, you try to see if among a, d, e, h, u there are at least two numbers make the 2nd MSB differs, if yes, then definitely, the 2nd MSB will be set in the final result. And maybe at this point the candidate group shinks from a,d,e,h,u to a, e, h. Implicitly, every iteration, you are narrowing down the candidate group, but you don't need to track how the group is shrinking, you only cares about the final result.

@dribvurhd This is (32n), which is still O(n). The length of Integer when handle as Byte is 32.

Excellent code. Add some explanation here with one example. Hope this will be helpful.
public class Solution { public int findMaximumXOR(int[] nums) { int max = 0, mask = 0; for (int i = 31; i >= 0; i) { mask = (1 << i); HashSet<Integer> set = new HashSet<Integer>(); for (int num : nums) { set.add(num & 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 = max  (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max for (int prefix : set) { if (set.contains(tmp ^ prefix)) { max = tmp; } } } return max; } }
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

@Joyce_Lee said in Java O(n) solution using bit manipulation and HashMap:
set.add(num & mask);
Hi Joyce, since only the AND of the current num and the mask is being added to the SET, wouldn't the SET only have 2 values?
if mask is '1000', then only 1000 and/or 0000
if mask is '0100', then only 0100 and/or 0000
I'm trying to fully understand the solution, appreciate any feedback! thanks!





@Joyce_Lee Hello, your example is wrong. When i=0, max should be 1100. I stock on this example and realize the number is wrong, but thanks for your explanation.


C++ version of your solution with some comments. I have to put the hash set outside the loop otherwise the OJ gives me MLE.
int findMaximumXOR(vector<int>& nums) { int max = 0, mask = 0; unordered_set<int> t; // search from left to right, find out for each bit is there // two numbers that has different value for (int i = 31; i >= 0; i){ // mask contains the bits considered so far mask = (1 << i); t.clear(); // store prefix of all number with right i bits discarded for (int n: nums){ t.insert(mask & n); } // now find out if there are two prefix with different ith bit // if there is, the new max should be current max with one 1 bit at ith position, which is candidate // and the two prefix, say A and B, satisfies: // A ^ B = candidate // so we also have A ^ candidate = B or B ^ candidate = A // thus we can use this method to find out if such A and B exists in the set int candidate = max  (1<<i); for (int prefix : t){ if (t.find(prefix ^ candidate) != t.end()){ max = candidate; break; } } } return max; }


@robert501128 I have been breaking my head to understand,how XOR of the two number in the array is replaced by this code snippet. I know the trick here revolves around "a^b=c, then a^c=b, b^c=a",but it will be great if you can explain what a,b &c corresponds to in the example which joyce_Lee explained in the previous threads.
