Skip to content
RED SAGSkills
hard60 ptsbit-manipulationtriegreedy

Largest XOR of Two Numbers

Given an array of non-negative integers nums, return the largest value of nums[i] XOR nums[j] over all pairs with i <= j (so a single-element array gives 0).

A brute-force check of every pair is too slow for large inputs; aim for about 31 steps per number.

Example 1

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

Example 2

Input: nums = [0]
Output: 0

Constraints

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

Insert every number into a binary trie, most significant bit first.

Hint 2

For each number, walk the trie greedily choosing the opposite bit whenever possible; that maximises the XOR from the top bit down.

Discussion 0

Join free to post in the discussion.

Good practice for: Embedded Systems Engineer, Blockchain Developer, Backend Developer, Game Developer, Machine Learning Engineer

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.