Maximum XOR of Two Numbers in an Array
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
0 ≤ nums[i] ≤ 10⁹
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Pair
BruteCompare every pair directly — for each i, XOR it against every later j, and keep the largest result seen. Correct, but for even a few thousand elements that's millions of pairwise comparisons for a value that could be pinned down one bit at a time instead.
O(n²)O(1) extra1class Solution {
2 public int maximumXor(int[] nums) {
3 int maxXor = 0;
4 for (int i = 0; i < nums.length; i++) {
5 for (int j = i + 1; j < nums.length; j++) {
6 maxXor = Math.max(maxXor, nums[i] ^ nums[j]);
7 }
8 }
9 return maxXor;
10 }
11}Optimal — Bit-by-Bit Greedy Prefix Matching
OptimalBuild the answer one bit at a time, from the most significant bit down. At each step, tentatively assume the current best answer can gain this next bit, then check whether that's actually achievable — by truncating every value to just the bits decided so far and testing whether two of those truncated prefixes XOR together to produce the candidate. Lock the bit in only when a real pair backs it up; otherwise leave it at 0 and move to the next bit regardless.
O(n)O(n)1class Solution {
2 public int maximumXor(int[] nums) {
3 int maxXor = 0;
4 int mask = 0;
5 for (int bit = 31; bit >= 0; bit--) {
6 mask |= (1 << bit);
7 Set<Integer> prefixes = new HashSet<>();
8 for (int num : nums) {
9 prefixes.add(num & mask);
10 }
11 int candidate = maxXor | (1 << bit);
12 for (int prefix : prefixes) {
13 if (prefixes.contains(candidate ^ prefix)) {
14 maxXor = candidate;
15 break;
16 }
17 }
18 }
19 return maxXor;
20 }
21}