Strongest XOR Pair

MediumTries & Strings

Problem

Given an array of non-negative integers nums, return the largest value of nums[i] XOR nums[j] over all 0 ≤ i ≤ j < n.

Choosing the same element twice gives 0, so the answer is at least 0.

Example 1

Input:
nums = [6, 9, 12, 3]
Output:
15

6 XOR 9 = 0110 XOR 1001 = 1111 = 15.

Example 2

Input:
nums = [1, 2, 4]
Output:
6

Example 3

Input:
nums = [7]
Output:
0

Constraints

  • 1 ≤ nums.length ≤ 2·10^4
  • 0 ≤ nums[i] ≤ 2^31 - 1

Hint

Show the first hint

A high bit set in the result is worth more than all lower bits together.

Walkthrough

How to approach it

01Clarify before coding

  • Can i equal j? Yes, which makes 0 the minimum possible answer.
  • Are numbers non-negative? Yes, at most 31 bits.
  • Return the value or the indices? The value.

02Brute force

XOR every pair and keep the maximum.

Cost: O(n²): 2·10^8 pairs for n = 2·10^4.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.