Maximum XOR of Two Numbers in an Array

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Examples

Example 1:

1
2
3
4
5


Input:
nums = [3,10,5,25,2,8]
Output:
 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

1
2
3
4


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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 } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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.

Problem#

Examples#

Solution#

Method 1 – Trie-based Greedy Bitwise Search#

Intuition#

Approach#

Code#

Complexity#