Maximum XOR of Two Numbers in an Array
Maximum XOR of Two Numbers in an Array is a medium tries problem solved with the bitwise trie pattern.
The best approach, optimal (binary trie, greedy from the top bit), runs in O(n · 31) time and O(n · 31) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
You are given an array nums of non-negative integers. Return the largest value of nums[i] XOR nums[j] over all index pairs with 0 <= i <= j < nums.length.
Note that i and j may be the same index, so the answer is never negative and is 0 when the array has only one number.
Examples
Example 1
- Input
nums = [6, 9, 12, 3]- Output
15- Why
- 6 XOR 9 = 0110 XOR 1001 = 1111 = 15, and 12 XOR 3 is also 15. No pair can beat 4 set bits here.
Example 2
- Input
nums = [8, 1, 2, 20]- Output
28- Why
- 20 XOR 8 = 10100 XOR 01000 = 11100 = 28. The next best pair, 20 XOR 2, only reaches 22.
Example 3
- Input
nums = [7]- Output
0- Why
- With a single number the only pair is the number with itself, and x XOR x = 0.
Constraints
1 <= nums.length <= 2 * 10^50 <= nums[i] <= 2^31 - 1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Optimal (binary trie, greedy from the top bit) | O(n · 31) | O(n · 31) |
1Brute force
O(n²)Every one of the n(n - 1) / 2 pairs is XORed once.O(1)Only the running maximum.Try every pair of indices and keep the largest XOR.
- best = 0.
- For every i and every j > i, best = max(best, nums[i] ^ nums[j]).
- Return best.
class Solution {
public int findMaximumXOR(int[] nums) {
int best = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
best = Math.max(best, nums[i] ^ nums[j]);
}
}
return best;
}
}class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
best = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
best = max(best, nums[i] ^ nums[j])
return bestclass Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int best = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
best = max(best, nums[i] ^ nums[j]);
}
}
return best;
}
};function findMaximumXOR(nums) {
let best = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
best = Math.max(best, nums[i] ^ nums[j]);
}
}
return best;
}2Optimal (binary trie, greedy from the top bit)
O(n · 31)Each number does one insert and one query, each 31 steps long.O(n · 31)Each insert can create up to 31 new trie nodes.Insert each number into a trie keyed by its bits from bit 30 down to bit 0. For a query x, walk from the root and at every level take the child whose bit is the opposite of x's bit if it exists (that bit of the XOR becomes 1), otherwise take the same bit. Because a higher bit outweighs all lower bits combined, this greedy walk finds the best partner for x. Insert x before querying it so the trie is never empty.
- Build trie nodes as arrays of two children, stored in flat int arrays for speed.
- For each x: insert its 31 bits, then walk the trie choosing the opposite bit when possible, adding (1 << b) to the XOR each time it succeeds.
- Keep the maximum XOR over all x.
class Solution {
public int findMaximumXOR(int[] nums) {
int maxNodes = nums.length * 31 + 1;
int[][] child = new int[2][maxNodes];
int count = 1; // node 0 is the root
int best = 0;
for (int x : nums) {
int node = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
if (child[bit][node] == 0) child[bit][node] = count++;
node = child[bit][node];
}
node = 0;
int cur = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
int want = bit ^ 1;
if (child[want][node] != 0) {
cur |= 1 << b;
node = child[want][node];
} else {
node = child[bit][node];
}
}
best = Math.max(best, cur);
}
return best;
}
}class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
max_nodes = len(nums) * 31 + 1
child = [[0] * max_nodes, [0] * max_nodes]
count = 1 # node 0 is the root
best = 0
for x in nums:
node = 0
for b in range(30, -1, -1):
bit = (x >> b) & 1
if child[bit][node] == 0:
child[bit][node] = count
count += 1
node = child[bit][node]
node = 0
cur = 0
for b in range(30, -1, -1):
bit = (x >> b) & 1
want = bit ^ 1
if child[want][node] != 0:
cur |= 1 << b
node = child[want][node]
else:
node = child[bit][node]
best = max(best, cur)
return bestclass Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int maxNodes = nums.size() * 31 + 1;
vector<int> child0(maxNodes, 0), child1(maxNodes, 0);
vector<int>* child[2] = {&child0, &child1};
int count = 1; // node 0 is the root
int best = 0;
for (int x : nums) {
int node = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
if ((*child[bit])[node] == 0) (*child[bit])[node] = count++;
node = (*child[bit])[node];
}
node = 0;
int cur = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
int want = bit ^ 1;
if ((*child[want])[node] != 0) {
cur |= 1 << b;
node = (*child[want])[node];
} else {
node = (*child[bit])[node];
}
}
best = max(best, cur);
}
return best;
}
};function findMaximumXOR(nums) {
const maxNodes = nums.length * 31 + 1;
const child = [new Int32Array(maxNodes), new Int32Array(maxNodes)];
let count = 1; // node 0 is the root
let best = 0;
for (const x of nums) {
let node = 0;
for (let b = 30; b >= 0; b--) {
const bit = (x >> b) & 1;
if (child[bit][node] === 0) child[bit][node] = count++;
node = child[bit][node];
}
node = 0;
let cur = 0;
for (let b = 30; b >= 0; b--) {
const bit = (x >> b) & 1;
const want = bit ^ 1;
if (child[want][node] !== 0) {
cur |= 1 << b;
node = child[want][node];
} else {
node = child[bit][node];
}
}
best = Math.max(best, cur);
}
return best;
}Edge cases to test
- A single element (answer 0, since i may equal j)
- All elements equal (answer 0)
- Zero in the array (its XOR with x is x itself)
- Numbers using bit 30, the highest bit allowed
Hints
Hint 1
The highest bit of the result matters more than all lower bits together. Try to make the top bit 1 first, then the next, and so on.
Hint 2
For a fixed number x, the best partner has the opposite bit to x wherever possible, starting from the top bit.
Hint 3
Store every number in a binary trie of its 31 bits. Walking down from the root, prefer the child with the opposite bit.
FAQ
What is the best time complexity for Maximum XOR of Two Numbers in an Array?
Optimal (binary trie, greedy from the top bit) runs in O(n · 31) time and O(n · 31) extra space. Each number does one insert and one query, each 31 steps long.
Which pattern does Maximum XOR of Two Numbers in an Array use?
It is a tries problem that uses the bitwise trie pattern.
Is there a brute force solution for Maximum XOR of Two Numbers in an Array?
Yes. Brute force takes O(n²) time and O(1) space. Try every pair of indices and keep the largest XOR.
Which edge cases should I test for Maximum XOR of Two Numbers in an Array?
A single element (answer 0, since i may equal j); All elements equal (answer 0); Zero in the array (its XOR with x is x itself); Numbers using bit 30, the highest bit allowed.