We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum XOR With an Element From Array

Difficulty: Hard

Problem Description

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 ith query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed 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 ith query.

Key Insights

  • The problem requires finding the maximum XOR of a given number with elements from an array while respecting a maximum threshold.
  • We can utilize a Trie (prefix tree) to efficiently find the maximum XOR, as it allows for bitwise comparisons.
  • Sorting the nums array helps in quickly filtering out elements based on the maximum threshold m_i.
  • The XOR operation tends to yield high values when the bits differ, making it essential to choose the optimal element from nums for each query.

Space and Time Complexity

Time Complexity: O(n log n + q log n) where n is the length of nums and q is the length of queries, due to sorting and querying in the Trie. Space Complexity: O(n) for storing the Trie.

Solution

To solve this problem, we will use a Trie data structure to store the binary representations of the numbers in nums. By doing this, we can efficiently query the maximum XOR value for each x_i in the queries against the elements of nums that are less than or equal to m_i.

  1. Insert Elements into Trie: Insert each number from nums into the Trie. Each number is represented in binary form, allowing for efficient bitwise operations.
  2. Sort nums: Sort nums to facilitate the quick retrieval of elements that do not exceed m_i.
  3. Query the Trie: For each query, filter the sorted nums to include only those that are less than or equal to m_i and then use the Trie to find the maximum XOR for x_i.
  4. Return Results: Collect the results for each query and return them as an array.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

def maximizeXor(nums, queries):
    nums.sort()  # Sort nums for efficient filtering
    trie = Trie()
    results = []
    for x, m in queries:
        # Insert elements into the trie that are <= m
        for num in nums:
            if num > m:
                break
            trie.insert(num)
        # Find the maximum XOR for current query
        results.append(trie.max_xor(x))
        trie = Trie()  # Reset trie for the next query
    return results
← Back to All Questions