Jobs

Interviews

Discussions

Maximum XOR of Two Numbers in an Array

Medium

Google

1 view

Topics:

ArraysBit ManipulationTrees

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

For example:

nums = [3,10,5,25,2,8] The maximum result is 5 XOR 25 = 28.
nums = [14,70,53,83,49,91,36,80,92,51,66,70] The maximum result is 127.

Could you provide a solution that efficiently finds the maximum XOR value, considering the constraints that 1 <= nums.length <= 2 * 10^5 and 0 <= nums[i] <= 2^31 - 1?

Maximum XOR of Two Numbers in an Array

Medium

Google

1 view

Topics:

ArraysBit ManipulationTrees

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

For example:

nums = [3,10,5,25,2,8] The maximum result is 5 XOR 25 = 28.
nums = [14,70,53,83,49,91,36,80,92,51,66,70] The maximum result is 127.

Could you provide a solution that efficiently finds the maximum XOR value, considering the constraints that 1 <= nums.length <= 2 * 10^5 and 0 <= nums[i] <= 2^31 - 1?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of an element in the `nums` array? This will help me understand the bit representation I need to consider.
Can the input array `nums` be empty or null?
Are all the numbers in the array non-negative integers as specified, or could there be other data types?
If the array contains only one number, what should the function return?
Are there any specific memory constraints I should be aware of, considering the potential size of the input array?

Brute Force Solution

Approach

The brute force approach for this problem is simple: try every possible pair of numbers. For each pair, calculate their XOR value and keep track of the largest XOR value you find.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Compare it to every other number in the collection, one at a time.
For each comparison, calculate a special value based on these two numbers.
If the special value is the biggest one we've seen so far, remember it.
Now take the second number in the collection.
Again, compare it to every other number in the collection.
Calculate the special value for each comparison.
If we find a special value bigger than the biggest one we previously remembered, update our memory.
Keep doing this process with each number in the collection, making sure it is compared against all other numbers.
After comparing all possible pairs of numbers, the largest special value we remembered is the answer.

Code Implementation

def maximum_xor_brute_force(numbers):
    max_xor_value = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the first number against all other numbers
        for second_number_index in range(len(numbers)):

            # Calculate the XOR value for the pair
            current_xor_value = numbers[first_number_index] ^ numbers[second_number_index]

            # Update max_xor_value if a larger value is found
            if current_xor_value > max_xor_value:
                max_xor_value = current_xor_value

    return max_xor_value

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the array of size n. For each element, it compares it with every other element in the array to find the maximum XOR value. This results in a nested loop structure where for each of the n elements, we perform approximately n comparisons. Therefore, the total number of operations is proportional to n * n, leading to a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through pairs of numbers in the input array. It only uses a variable to store the maximum XOR value found so far, and possibly index variables for the loops. The amount of auxiliary space used does not depend on the input size N (where N is the number of elements in the array), as it always uses a fixed number of variables. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to find two numbers in a list that, when combined using a special operation called XOR, give the largest possible result. Instead of checking every pair of numbers, we use a clever trick involving building the largest XOR value bit by bit from left to right.

Here's how the algorithm would work step-by-step:

Start by assuming the maximum XOR result is zero.
Consider the most significant bit (the leftmost bit) of each number in the list.
Imagine building the maximum XOR value bit by bit. For the most significant bit, check if it's possible to get a '1' in that position.
To get a '1' in the most significant bit of the XOR result, you need two numbers in the list where one has a '0' and the other has a '1' in that position. If such a pair exists, update our current maximum XOR result to have a '1' in that position.
Move to the next bit (to the right) and repeat the process. At each step, try to see if it's possible to make that bit a '1' in the XOR result, given the choices we've already made for the bits to the left.
Keep going through all the bits from left to right. By the end, you will have constructed the largest possible XOR value you can achieve from any two numbers in the list.

Code Implementation

def find_maximum_xor(numbers):
    maximum_xor_result = 0
    mask = 0

    # Iterate from the most significant bit to the least significant bit
    for i in range(31, -1, -1):
        # Update the mask to include the current bit
        mask |= (1 << i)

        prefixes = set()
        # Store all prefixes of the numbers with the current mask
        for number in numbers:
            prefixes.add(number & mask)

        # Try to find a number that, when XORed with the current prefix,
        # results in the current maximum XOR with the current bit set to 1
        potential_maximum_xor = maximum_xor_result | (1 << i)
        for prefix in prefixes:
            if (potential_maximum_xor ^ prefix) in prefixes:
                # If such a number exists, update the maximum XOR
                maximum_xor_result = potential_maximum_xor

                break

    return maximum_xor_result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the bits of the numbers in the array from left to right. For each bit position, it iterates through the array of n numbers to build a set of prefixes. Then, for each bit, it checks if there exists a pair of prefixes in the set that can produce a '1' in that bit position of the maximum XOR value. This check involves iterating through the set of prefixes again in a single inner loop, resulting in O(n) complexity for each bit. Since the number of bits is constant (usually 32 for integers), the overall time complexity is O(n * constant), which simplifies to O(n).

Space Complexity

O(N) – The algorithm implicitly uses a set (or a similar data structure like a hash table) to store the prefixes of the numbers encountered so far in each bit iteration. In the worst case, for each bit, it might store prefixes of all N numbers in the input array, leading to a space complexity proportional to the number of elements N. Therefore, the auxiliary space used by the set can grow linearly with the input size. This makes the space complexity O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no XOR operation is possible.
Input array with a single element	Return 0 since XOR requires two elements.
Array contains only zeros	Return 0 as 0 XOR 0 is 0.
Array with maximum integer values (e.g., all 2147483647)	The XOR operation will produce a result within the integer range; handle potential integer overflow by ensuring use of unsigned integers if needed, or by using a larger data type like 'long' if language specific integer max values are small.
Array with minimum integer values (e.g., all -2147483648)	The problem specifies non-negative integers, so this should not occur, but the solution should define what an error state is and gracefully handle it.
Large input array (e.g., 100,000 elements)	The time complexity should be considered; a naive O(n^2) solution will likely time out, therefore Trie or hash-based approaches are favored for performance.
Array with elements that result in XOR exceeding maximum integer value (if negative numbers were allowed).	Since the input is non-negative, the XOR will always be non-negative and less than twice the maximum value of any element; this scenario is irrelevant with the non-negative constraint, however, the chosen data type for storing the XOR result needs to be large enough to handle the maximum potential value.
Array containing duplicate numbers.	Duplicate numbers do not affect the correctness of the trie or greedy algorithm as they are treated as distinct elements during the XOR operations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of an element in the `nums` array? This will help me understand the bit representation I need to consider.
Can the input array `nums` be empty or null?
Are all the numbers in the array non-negative integers as specified, or could there be other data types?
If the array contains only one number, what should the function return?
Are there any specific memory constraints I should be aware of, considering the potential size of the input array?

Brute Force Solution

Approach

The brute force approach for this problem is simple: try every possible pair of numbers. For each pair, calculate their XOR value and keep track of the largest XOR value you find.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Compare it to every other number in the collection, one at a time.
For each comparison, calculate a special value based on these two numbers.
If the special value is the biggest one we've seen so far, remember it.
Now take the second number in the collection.
Again, compare it to every other number in the collection.
Calculate the special value for each comparison.
If we find a special value bigger than the biggest one we previously remembered, update our memory.
Keep doing this process with each number in the collection, making sure it is compared against all other numbers.
After comparing all possible pairs of numbers, the largest special value we remembered is the answer.

Code Implementation

def maximum_xor_brute_force(numbers):
    max_xor_value = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the first number against all other numbers
        for second_number_index in range(len(numbers)):

            # Calculate the XOR value for the pair
            current_xor_value = numbers[first_number_index] ^ numbers[second_number_index]

            # Update max_xor_value if a larger value is found
            if current_xor_value > max_xor_value:
                max_xor_value = current_xor_value

    return max_xor_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by assuming the maximum XOR result is zero.
Consider the most significant bit (the leftmost bit) of each number in the list.
Imagine building the maximum XOR value bit by bit. For the most significant bit, check if it's possible to get a '1' in that position.
To get a '1' in the most significant bit of the XOR result, you need two numbers in the list where one has a '0' and the other has a '1' in that position. If such a pair exists, update our current maximum XOR result to have a '1' in that position.
Move to the next bit (to the right) and repeat the process. At each step, try to see if it's possible to make that bit a '1' in the XOR result, given the choices we've already made for the bits to the left.
Keep going through all the bits from left to right. By the end, you will have constructed the largest possible XOR value you can achieve from any two numbers in the list.

Code Implementation

def find_maximum_xor(numbers):
    maximum_xor_result = 0
    mask = 0

    # Iterate from the most significant bit to the least significant bit
    for i in range(31, -1, -1):
        # Update the mask to include the current bit
        mask |= (1 << i)

        prefixes = set()
        # Store all prefixes of the numbers with the current mask
        for number in numbers:
            prefixes.add(number & mask)

        # Try to find a number that, when XORed with the current prefix,
        # results in the current maximum XOR with the current bit set to 1
        potential_maximum_xor = maximum_xor_result | (1 << i)
        for prefix in prefixes:
            if (potential_maximum_xor ^ prefix) in prefixes:
                # If such a number exists, update the maximum XOR
                maximum_xor_result = potential_maximum_xor

                break

    return maximum_xor_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no XOR operation is possible.
Input array with a single element	Return 0 since XOR requires two elements.
Array contains only zeros	Return 0 as 0 XOR 0 is 0.
Array with maximum integer values (e.g., all 2147483647)	The XOR operation will produce a result within the integer range; handle potential integer overflow by ensuring use of unsigned integers if needed, or by using a larger data type like 'long' if language specific integer max values are small.
Array with minimum integer values (e.g., all -2147483648)	The problem specifies non-negative integers, so this should not occur, but the solution should define what an error state is and gracefully handle it.
Large input array (e.g., 100,000 elements)	The time complexity should be considered; a naive O(n^2) solution will likely time out, therefore Trie or hash-based approaches are favored for performance.
Array with elements that result in XOR exceeding maximum integer value (if negative numbers were allowed).	Since the input is non-negative, the XOR will always be non-negative and less than twice the maximum value of any element; this scenario is irrelevant with the non-negative constraint, however, the chosen data type for storing the XOR result needs to be large enough to handle the maximum potential value.
Array containing duplicate numbers.	Duplicate numbers do not affect the correctness of the trie or greedy algorithm as they are treated as distinct elements during the XOR operations.