Maximum XOR of Two Numbers in an Array
MediumUpdated: Aug 6, 2025
Practice on:
Problem
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Examples
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
Solution
Method 1 – Trie-based Greedy Bitwise Search
Intuition
To maximize XOR between two numbers, we want their bits to differ as much as possible. By building a Trie of all numbers' binary representations, for each number, we can greedily search for the number in the Trie that differs at each bit, maximizing the XOR.
Approach
- Build a Trie where each path from root to leaf represents a number in binary.
- For each number, traverse the Trie, at each bit preferring the opposite bit if possible, to maximize XOR.
- Track the maximum XOR found.
Code
C++
class Trie {
public:
Trie* children[2];
Trie() : children{nullptr, nullptr} {}
void insert(int x) {
Trie* node = this;
for (int i = 30; ~i; --i) {
int v = x >> i & 1;
if (!node->children[v]) node->children[v] = new Trie();
node = node->children[v];
}
}
int search(int x) {
Trie* node = this;
int ans = 0;
for (int i = 30; ~i; --i) {
int v = x >> i & 1;
if (node->children[v ^ 1]) {
ans |= 1 << i;
node = node->children[v ^ 1];
} else {
node = node->children[v];
}
}
return ans;
}
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
Trie* trie = new Trie();
int ans = 0;
for (int x : nums) {
trie->insert(x);
ans = max(ans, trie->search(x));
}
return ans;
}
};
Go
type Trie struct {
children [2]*Trie
}
func newTrie() *Trie { return &Trie{} }
func (t *Trie) insert(x int) {
node := t
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (t *Trie) search(x int) int {
node := t
ans := 0
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v^1] != nil {
ans |= 1 << i
node = node.children[v^1]
} else {
node = node.children[v]
}
}
return ans
}
func findMaximumXOR(nums []int) int {
trie := newTrie()
ans := 0
for _, x := range nums {
trie.insert(x)
ans = max(ans, trie.search(x))
}
return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }
Java
class Trie {
private Trie[] children = new Trie[2];
public Trie() {}
public void insert(int x) {
Trie node = this;
for (int i = 30; i >= 0; --i) {
int v = x >> i & 1;
if (node.children[v] == null) node.children[v] = new Trie();
node = node.children[v];
}
}
public int search(int x) {
Trie node = this;
int ans = 0;
for (int i = 30; i >= 0; --i) {
int v = x >> i & 1;
if (node.children[v ^ 1] != null) {
ans |= 1 << i;
node = node.children[v ^ 1];
} else {
node = node.children[v];
}
}
return ans;
}
}
class Solution {
public int findMaximumXOR(int[] nums) {
Trie trie = new Trie();
int ans = 0;
for (int x : nums) {
trie.insert(x);
ans = Math.max(ans, trie.search(x));
}
return ans;
}
}
Kotlin
class Trie {
val children = arrayOfNulls<Trie>(2)
fun insert(x: Int) {
var node = this
for (i in 30 downTo 0) {
val v = (x shr i) and 1
if (node.children[v] == null) node.children[v] = Trie()
node = node.children[v]!!
}
}
fun search(x: Int): Int {
var node = this
var ans = 0
for (i in 30 downTo 0) {
val v = (x shr i) and 1
if (node.children[v xor 1] != null) {
ans = ans or (1 shl i)
node = node.children[v xor 1]!!
} else {
node = node.children[v]!!
}
}
return ans
}
}
class Solution {
fun findMaximumXOR(nums: IntArray): Int {
val trie = Trie()
var ans = 0
for (x in nums) {
trie.insert(x)
ans = maxOf(ans, trie.search(x))
}
return ans
}
}
Python
class Trie:
def __init__(self):
self.children = [None, None]
def insert(self, x: int):
node = self
for i in range(30, -1, -1):
v = x >> i & 1
if node.children[v] is None:
node.children[v] = Trie()
node = node.children[v]
def search(self, x: int) -> int:
node = self
ans = 0
for i in range(30, -1, -1):
v = x >> i & 1
if node.children[v ^ 1]:
ans |= 1 << i
node = node.children[v ^ 1]
else:
node = node.children[v]
return ans
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
trie = Trie()
ans = 0
for x in nums:
trie.insert(x)
ans = max(ans, trie.search(x))
return ans
Rust
struct Trie {
children: [Option<Box<Trie>>; 2],
}
impl Trie {
fn new() -> Trie {
Trie { children: [None, None] }
}
fn insert(&mut self, x: i32) {
let mut node = self;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if node.children[v].is_none() {
node.children[v] = Some(Box::new(Trie::new()));
}
node = node.children[v].as_mut().unwrap();
}
}
fn search(&self, x: i32) -> i32 {
let mut node = self;
let mut ans = 0;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if let Some(child) = &node.children[v ^ 1] {
ans |= 1 << i;
node = child.as_ref();
} else {
node = node.children[v].as_ref().unwrap();
}
}
ans
}
}
struct Solution;
impl Solution {
pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
let mut trie = Trie::new();
let mut ans = 0;
for &x in &nums {
trie.insert(x);
ans = ans.max(trie.search(x));
}
ans
}
}
TypeScript
class Trie {
children: [Trie | null, Trie | null] = [null, null];
insert(x: number) {
let node: Trie = this;
for (let i = 30; i >= 0; --i) {
const v = (x >> i) & 1;
if (!node.children[v]) node.children[v] = new Trie();
node = node.children[v]!;
}
}
search(x: number): number {
let node: Trie = this;
let ans = 0;
for (let i = 30; i >= 0; --i) {
const v = (x >> i) & 1;
if (node.children[v ^ 1]) {
ans |= 1 << i;
node = node.children[v ^ 1]!;
} else {
node = node.children[v]!;
}
}
return ans;
}
}
class Solution {
findMaximumXOR(nums: number[]): number {
const trie = new Trie();
let ans = 0;
for (const x of nums) {
trie.insert(x);
ans = Math.max(ans, trie.search(x));
}
return ans;
}
}
Complexity
- Time Complexity: O(N * W), where N is the number of elements and W is the bit-width (here, 31).
- Space Complexity: O(N * W), for the Trie storing all numbers.