Algorithm
Problem Name: 421. Maximum XOR of Two Numbers in an Array
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int qBitPartition(int* a, int l, int r, int bc) {
if (a == NULL || l > r || bc >= 32 || bc < 0) return -1;
int i = l;
int j = r;
while (i < j) {
while (i < j && !(a[i] & (1 << bc))) i ++;
while (i < j && (a[j] & (1 << bc))) j --;
if (i < j) {
// swap them
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
i ++;
j --;
}
}
// in case all elements fall into the first part
if (!(a[i] & (1 << bc))) i ++;
return i; // start of the second partition
}
// one number is selected from l1~r1
// the other numbser is selected from l2~r2
int findPartitionMaxXor(int* a, int l1, int r1, int l2, int r2, int bc) {
// one of these two partitions has no data, the max must be in the other two partitions
if (l1 > r1 || l2 > r2) return 0;
// the only difference is the last bit, pick any number from either parition and xor them
if (bc < 0) return a[l1] ^ a[l2];
// converge here!!!
if (l1 == r1 && l2 == r2) return a[l1] ^ a[l2];
// find next available partition, jump over all zero bits
do {
int p1 = qBitPartition(a, l1, r1, bc);
int p2 = qBitPartition(a, l2, r2, bc);
if ((p1-1 >= l1 && r2 >= p2) ||
(r1 >= p1 && p2-1 >= l2)) {
// as long as at least a new partition is formed, let's recursive.
int max1 = findPartitionMaxXor(a, l1, p1-1, p2, r2, bc - 1);
int max2 = findPartitionMaxXor(a, p1, r1, l2, p2-1, bc - 1);
return max1 > max2 ? max1 : max2;
}
bc --; // no new partition is formed on this bit, let's continue on other bits.
} while(bc >= 0);
return 0;
}
int findMaximumXOR(int* nums, int numsSize) {
int bc = 31;
int p;
// we must find a no empty partition first
while (bc >= 0) {
p = qBitPartition(nums, 0, numsSize-1, bc);
if (p > 0 && p < numsSize) {
return findPartitionMaxXor(nums, 0, p-1, p, numsSize-1, bc - 1);
}
bc--;
}
return 0; // all bits are same, a ^ a is 0.
}
Input
nums = [3,10,5,25,2,8]
Output
28
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findMaximumXOR(int[] nums) {
if (nums.length == 0) {
return 0;
}
Trie root = new Trie();
for (int num : nums) {
Trie curr = root;
for (int i = 31; i >= 0; i--) {
int currBit = (num >>> i) & 1;
if (curr.children[currBit] == null) {
curr.children[currBit] = new Trie();
}
curr = curr.children[currBit];
}
}
int maxVal = Integer.MIN_VALUE;
for (int num : nums) {
Trie curr = root;
int currVal = 0;
for (int i = 31; i >= 0; i--) {
int currBit = (num >>> i) & 1;
if (curr.children[currBit ^ 1] != null) {
currVal += (1 << i);
curr = curr.children[currBit ^ 1];
}
else {
curr = curr.children[currBit];
}
}
maxVal = Math.max(maxVal, currVal);
}
return maxVal;
}
}
class Trie {
Trie[] children;
public Trie() {
children = new Trie[2];
}
}
Input
nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output
127
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findMaximumXOR = function(nums) {
let res = 0, mask = 0
for(let i = 31; i >= 0; i--) {
mask = mask | (1 << i)
const set = new Set()
for(let e of nums) set.add(e & mask)
const tmp = res | (1 << i)
for(let e of set) {
if(set.has(e ^ tmp)) {
res = tmp
break
}
}
}
return res
};
Input
nums = [3,10,5,25,2,8]
Output
28
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findMaximumXOR(self, nums, ans = 0):
ans = 0
for bit in range(30, -1, -1):
ans <<= 1
attempt = ans | 1
prefix = set()
for x in nums:
p = x >> bit
if attempt ^ p in prefix:
ans = attempt
break
prefix.add(p)
return ans
Input
nums = [3,10,5,25,2,8]
Output
28
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0421_MaximumXOROfTwoNumbersInAnArray
{
public int FindMaximumXOR(int[] nums)
{
var set = new HashSet < int>(nums.Length);
int ret = 0, mask = 0;
for (int i = 31; i >= 0; --i)
{
mask |= 1 << i;
foreach (int num in nums)
set.Add(num & mask);
int find = ret | (1 << i);
foreach (int num in set)
{
if (set.Contains(num ^ find))
{
ret = find;
break;
}
}
set.Clear();
}
return ret;
}
}
}
Input
nums = [3,10,5,25,2,8]
Output
28