Maximum XOR of Two Numbers in an Array

MEDIUM

Description

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

Approaches

Checkout 3 different approaches to solve Maximum XOR of Two Numbers in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward approach is to check every possible pair of numbers in the array. We can use two nested loops to iterate through all pairs (i, j), calculate nums[i] XOR nums[j], and keep track of the maximum value found.

Algorithm

Initialize a variable maxResult to 0.
Use two nested loops to iterate through all possible pairs of numbers (nums[i], nums[j]) in the array.
For each pair, calculate their XOR value: currentXOR = nums[i] ^ nums[j].
Compare currentXOR with maxResult and update maxResult if currentXOR is greater.
After checking all pairs, maxResult will hold the maximum XOR value.

This method exhaustively checks every unique pair of elements in the input array nums. It maintains a variable, maxResult, initialized to zero. The outer loop iterates from the first element to the last, and the inner loop iterates from the current element of the outer loop to the last. This ensures that each pair is considered exactly once (including a number with itself, which results in an XOR of 0). For each pair, their bitwise XOR is computed. If this result is larger than the current maxResult, maxResult is updated. This process guarantees that we find the maximum possible XOR value among all pairs.

class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxResult = 0;
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                maxResult = Math.max(maxResult, nums[i] ^ nums[j]);
            }
        }
        return maxResult;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in the array. This is because of the two nested loops, each iterating up to N times.Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space, making its space complexity constant.

Cons:

Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Maximum XOR of Two Numbers in an Array. Click on different languages to view the code.

class Trie { private Trie [] children = new Trie [ 2 ]; public Trie () { } public void insert ( int x ) { Trie node = this ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; } } public int search ( int x ) { Trie node = this ; int ans = 0 ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ^ 1 ] != null ) { ans |= 1 << i ; node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } } class Solution { public int findMaximumXOR ( int [] nums ) { Trie trie = new Trie (); int ans = 0 ; for ( int x : nums ) { trie . insert ( x ); ans = Math . max ( ans , trie . search ( x )); } return ans ; } }

Video Solution

Watch the video walkthrough for Maximum XOR of Two Numbers in an Array

Patterns:

Bit Manipulation

Data Structures:

ArrayHash TableTrie

Companies:

Goldman Sachs |