## 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 * 105`
• `0 <= 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.
}
``````
Copy The Code &

Input

cmd
nums = [3,10,5,25,2,8]

Output

cmd
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];
}
}
``````
Copy The Code &

Input

cmd
nums = [14,70,53,83,49,91,36,80,92,51,66,70]

Output

cmd
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--) {
const set = new Set()
const tmp = res | (1 << i)
for(let e of set) {
if(set.has(e ^ tmp)) {
res = tmp
break
}
}
}
return res
};
``````
Copy The Code &

Input

cmd
nums = [3,10,5,25,2,8]

Output

cmd
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
return ans
``````
Copy The Code &

Input

cmd
nums = [3,10,5,25,2,8]

Output

cmd
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)
{
foreach (int num in nums)

int find = ret | (1 << i);
foreach (int num in set)
{
if (set.Contains(num ^ find))
{
ret = find;
break;
}
}
set.Clear();
}
return ret;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [3,10,5,25,2,8]

Output

cmd
28