Skip to main content

421. Maximum XOR of Two Numbers in an Array

medium

Find the pair in an array whose XOR is largest. Brute force is O(n^2); the trie-on-bits trick brings it to O(32n) by greedily picking complementary bits.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 2^31 - 1

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force tries every pair — 2 * 10^5 squared is 4 * 10^10. TLE.

Hint 2

Greedy: build the answer bit by bit from the most significant bit, trying to set each bit if possible.

Hint 3

Use a hash set of prefixes. At bit k, partial answer is current_max | (1 << k). For every number n, check if (n's prefix XOR partial_answer) is also a known prefix — if yes, the bit is achievable.

Hint 4

Cleaner formulation: build a binary trie of all numbers' bits, then for each number greedily traverse the trie picking the opposite-bit child at every step.

Solution approach

Reveal approach

Bit-trie greedy approach. Insert every number's 32-bit binary representation into a trie keyed by bits from high to low. For each number, walk the trie from the root; at each bit, prefer the opposite-bit child (because XOR sets a bit when the operands differ) and accumulate the resulting XOR into a running best. The maximum over all walks is the answer. Each insert is O(32) and each query is O(32), so total is O(32n) = O(n) time and O(32n) trie space. The hash-set prefix variant achieves the same complexity with simpler code: for k from 31 down to 0, try to set the kth bit of the answer by checking whether two known prefixes XOR to the candidate.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • bit-manipulation
  • trie
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

More Bit Manipulation practice problems

See all Bit Manipulation problems →