Is Maximum XOR of Two Numbers in an Array easy or hard?

Maximum XOR of Two Numbers in an Array is generally classified as a medium difficulty problem. The brute force idea is straightforward, but identifying the Trie-based optimization requires understanding of bit manipulation and prefix tree structures.

How to solve Maximum XOR of Two Numbers in an Array in O(n)?

Use a binary Trie to store the bit representation of numbers as you iterate through the array. For each number, traverse the Trie preferring the opposite bit at each position to maximize XOR. Since each number processes at most 32 bits, the overall complexity becomes O(n * 32), which is effectively linear.

Maximum XOR of Two Numbers in an Array Python or Java solution?

Python and Java solutions typically implement the Trie-based method. Each number is inserted bit by bit into the Trie, and another traversal searches for the best complementary bits to maximize XOR. The algorithm runs in O(n * W) time and works efficiently even for large arrays.

What is the best approach for Maximum XOR of Two Numbers in an Array?

The most efficient approach uses a binary Trie built from the bit representation of numbers. For each number, you traverse the Trie and try to match opposite bits to maximize XOR at every position. This greedy bit strategy produces the optimal result with O(n * W) time complexity, where W is the number of bits (typically 32).

Is Maximum XOR of Two Numbers in an Array asked at Google Amazon Meta?

Maximum XOR of Two Numbers in an Array appears in technical interview preparation lists for companies such as Google, Amazon, and Meta. The problem tests bit manipulation skills, greedy reasoning, and familiarity with Trie data structures for efficient bitwise search.

What data structure is used in Maximum XOR of Two Numbers in an Array?

The optimal solution uses a binary Trie (also called a prefix tree) where each node represents a bit value 0 or 1. This structure allows fast traversal to find numbers with complementary bits, which maximizes the XOR value during comparison.

What is the time complexity of Maximum XOR of Two Numbers in an Array?

The brute force solution runs in O(n²) time because it compares every pair of elements. The optimized Trie-based approach runs in O(n * W) time, where W is the bit length of integers (usually 32). This effectively behaves like O(n) for typical constraints.

Description Solution Video 13:37

421. Maximum XOR of Two Numbers in an Array

Medium53.8% acceptance5 companies

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 * 10⁵
0 <= nums[i] <= 2³¹ - 1

Asked at 5 companies

Google Bloomberg Amazon Microsoft Meta

Topics

13:37

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

421. Maximum XOR of Two Numbers in an Array

Asked at 5 companies

Topics

Similar problems