Maximum XOR With an Element From Array

Hard

Asked by:

4 views

Topics:

ArraysBit Manipulation

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Try coding it in LeetCode

Maximum XOR With an Element From Array

Hard

Asked by:

4 views

Topics:

ArraysBit Manipulation

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Try coding it in LeetCode

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 are the ranges for the numbers in the input array and the query values?
Can the input array be empty, or can any of the query arrays be empty?
If there's no element in the array that satisfies the condition for a query, what should I return?
Are duplicate values allowed in the input array?
Is the array guaranteed to be sorted, or do I need to consider the unsorted case?

Brute Force Solution

Approach

The brute force method tries every possible number in the list against our input number to find the best pairing. We will try every single combination without any shortcuts to ensure we don't miss the maximum XOR result. This involves a direct, exhaustive comparison.

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

For each number we are given, we will examine every number in our list.
For each pair of numbers (the number we are given and a number from the list), perform the XOR operation.
Compare the result of the XOR operation with the biggest result we've seen so far.
If the current XOR result is bigger, remember this new result as the biggest.
After comparing the given number with every number in the list, make sure the numbers from the list are not larger than our given limit.
After checking every number from the original list, the biggest XOR result is the answer.

Code Implementation

def maximum_xor_with_element_from_array_brute_force(numbers, queries):
    results = []
    for query in queries:
        number = query[0]
        maximum_limit = query[1]
        maximum_xor_result = -1
        for list_number in numbers:
            #  Ensure that the number from the list is within the limit.
            if list_number <= maximum_limit:

                current_xor_result = number ^ list_number
                # Compare current XOR to existing XOR to keep track of maximum
                if current_xor_result > maximum_xor_result:

                    maximum_xor_result = current_xor_result

        results.append(maximum_xor_result)
    return results

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each number in the input array of size n. For each of these numbers, it then iterates through the entire array again to find the maximum XOR value that satisfies the constraint. Thus, there are nested loops where the outer loop iterates n times and the inner loop also iterates n times. Therefore, the total number of operations is proportional to n * n. This simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input array but doesn't use any auxiliary data structures beyond a few constant-sized variables. Specifically, the algorithm only stores the current XOR result and the maximum XOR result found so far. These variables occupy a constant amount of space, irrespective of the input array size. Therefore, the space complexity is O(1).

Optimal Solution

Approach

To efficiently find the maximum XOR value, we'll organize our numbers in a special tree-like structure called a Trie. This structure lets us quickly find the number that, when XORed with our target, gives us the highest possible result by walking down the Trie making greedy decisions at each step.

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

First, we sort the numbers we're working with, pairing them with their limits.
Create an empty Trie data structure.
Consider each target number and its limit, one at a time.
Before processing the current target, insert all numbers from our sorted list into the Trie that are less than or equal to the current limit.
For each target number, traverse the Trie to find the number that maximizes the XOR result.
Start from the most significant bit of the target number and Trie's root.
At each bit position, try to go to the opposite bit in the Trie. If we can't go to the opposite bit due to it not existing, go to the same bit.
The number formed by following this path in the Trie will maximize the XOR value.
Calculate the XOR of the target number and the number we found in the Trie.
Store the maximum XOR value for the current target.
After processing all the targets, return the list of maximum XOR values.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = [None] * 2

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, number):
        current_node = self.root
        for i in range(31, -1, -1):
            bit = (number >> i) & 1
            if not current_node.children[bit]:
                current_node.children[bit] = TrieNode()
            current_node = current_node.children[bit]

    def find_max_xor(self, number):
        current_node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (number >> i) & 1
            opposite_bit = 1 - bit

            if current_node.children[opposite_bit]:
                max_xor |= (1 << i)
                current_node = current_node.children[opposite_bit]
            else:
                current_node = current_node.children[bit]

        return max_xor

def max_xor_with_element(numbers, queries):
    numbers_with_limits = []
    for index, (value, limit) in enumerate(queries):
        numbers_with_limits.append((value, limit, index))

    numbers.sort()
    numbers_with_limits.sort(key=lambda x: x[1])

    trie = Trie()
    maximum_xors = [0] * len(queries)
    number_index = 0

    for value, limit, index in numbers_with_limits:
        # Insert elements into Trie that are <= current limit
        while number_index < len(numbers) and numbers[number_index] <= limit:
            trie.insert(numbers[number_index])
            number_index += 1

        # If the trie is empty, then we can't find any valid number
        if number_index == 0 and numbers[0] > limit:
            maximum_xors[index] = -1
            continue

        # Find maximum XOR for current value
        maximum_xors[index] = trie.find_max_xor(value)

    return maximum_xors

Big(O) Analysis

Time Complexity

O(n log n + m log n) – The initial sorting of the input array of size n takes O(n log n) time. The main loop iterates m times, where m is the number of queries. Inside the loop, inserting elements into the Trie takes O(log M) for each insertion, where M is the maximum value in the array (each number takes log M bits). Since we insert a maximum of n elements into the Trie for each query, the total insertion cost is n * O(log M). Querying the Trie to find the maximum XOR value for each query takes O(log M). Therefore, the total cost for m queries is m * (n * O(log M) + O(log M)). Assuming log M is proportional to log n in the problem, the complexity is O(n log n + m (n log n + log n)). If n > m, we can simplify this to O(n log n), otherwise, if m > n we have O(m n log n) which can be simplified to O(n log n + m log n) by considering the sorting part and the searching part which is the total time complexity.

Space Complexity

O(N) – The primary driver of auxiliary space is the Trie data structure. In the worst case, we insert all numbers from the input array into the Trie. Each number requires creating nodes along a path from the root to a leaf representing its binary representation. Since the numbers are integers and have a fixed number of bits (e.g., 32 bits), each insertion adds at most a constant number of nodes. Therefore, inserting N numbers can lead to at most O(N) nodes being created in the Trie, giving an overall auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Empty nums array	Return an empty list since no XOR operations are possible.
Empty queries array	Return an empty list as there are no queries to process.
nums array with one element	Iterate through queries and compare single element with limit for valid XOR, or return -1 if exceeds limit
Large nums array (scalability)	Trie-based solution provides logarithmic search, thus scaling effectively.
Large queries array (scalability)	Process each query independently, benefiting from the Trie's logarithmic search time.
nums array contains very large numbers (close to integer limit)	Trie should handle full integer bit representation to correctly compute XOR.
Numbers exceeding the bit length accounted for in the trie	Ensure the trie is constructed with enough bits to accommodate all numbers in the input.
Queries with small limits (close to zero)	The solution should correctly filter numbers that exceed the limit and return -1 when no valid XOR can be found.