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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum XOR for Each Query

Number: 1940

Difficulty: Medium

Paid? No

Companies: Bloomberg, Uber

Problem Description

Given a sorted array of non-negative integers nums and an integer maximumBit, you need to answer n queries. Each query consists of finding a non-negative integer k (with k < 2^(maximumBit)) such that when you XOR k with the XOR of all elements currently in nums, the result is maximized. After answering a query, the last element of nums is removed. Return an array answer where answer[i] is the result to the i-th query.

Key Insights

  • Compute the XOR of the entire array once.
  • A number k that maximizes (XOR sum of nums) XOR k is simply the bitwise complement of the XOR sum within the range [0, 2^(maximumBit)-1].
  • The bitmask (1 << maximumBit) - 1 represents the maximum value with maximumBit bits all set to 1.
  • After each query, update the cumulative XOR by removing the contribution of the removed (last) element.
  • Process the queries in order by simulating the removal from the end of the array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums, as we calculate the initial XOR then process each element once. Space Complexity: O(n) for storing the answer array (ignoring the space used for input).

Solution

We start by computing the cumulative XOR of all the numbers in nums. The maximum value that can be achieved by XORing with a number k (where k < 2^(maximumBit)) is obtained by flipping all the bits of the cumulative XOR within the range defined by maximumBit. This is done by XORing the cumulative XOR with the mask (which is (1 << maximumBit) - 1). For each query, we store the result and then remove the last element from nums by updating the cumulative XOR (using XOR with that element) before moving to the next query. Note that the queries are answered in the order of removal from the end of the array, which directly produces the answer sequence.

Code Solutions

# Python solution for Maximum XOR for Each Query

def maximumXorQueries(nums, maximumBit):
    # Compute the cumulative XOR of all elements in the array
    cumulative_xor = 0
    for num in nums:
        cumulative_xor ^= num  # update cumulative XOR
    
    # Create bitmask with maximumBit bits set to 1 (e.g., if maximumBit=3, mask=7 (111 in binary))
    mask = (1 << maximumBit) - 1
    n = len(nums)
    result = []
    
    # Process each query by removing the last element
    # Since the first query uses the full array, we simulate removals one by one
    for _ in range(n):
        # The k that maximizes the XOR value is the complement within the given bit range.
        k = cumulative_xor ^ mask
        result.append(k)
        # Remove the contribution of the last element (simulate removal from nums)
        cumulative_xor ^= nums.pop()
    return result

# Example Usage:
print(maximumXorQueries([0,1,1,3], 2))  # Expected Output: [0,3,2,3]
← Back to All Questions