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 Score Subarray Queries

Number: 3551

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of n non‐negative integers (nums) and many queries where each query gives a range [l, r], find for each query the maximum “XOR score” among all subarrays of nums[l..r]. The “XOR score” is defined as follows: starting with the subarray, repeatedly replace every element (except the last) with the XOR of that element and its next neighbor and then remove the last element; repeat until one number remains. For example, for the subarray [2,8,4] the score is 2 XOR 4 = 6.

It turns out that the final score of a subarray has a neat closed‐form: • For a subarray of length 1, the score is the single element. • For subarrays of length ≥2:  – If the length is even, the score equals the XOR of all its elements.  – If the length is odd, the score equals the XOR of its first and last element. Your task is to answer q queries efficiently.

Key Insights

  • The iterative process of applying pairwise XORs results in a closed form:   • For even-length subarrays: the final score is the XOR of all elements.   • For odd-length subarrays (length ≥3): the final score equals the XOR of the first and last elements.
  • Precompute prefix XORs to quickly calculate XOR over any subarray.
  • Use dynamic programming to precompute, for every possible subarray, the maximum XOR score. Since n ≤ 2000, an O(n^2) precomputation is acceptable, and each query (with q up to 10^5) can then be answered in O(1).

Space and Time Complexity

Time Complexity: O(n^2) for precomputing the answers for all subarrays and O(1) per query. Space Complexity: O(n^2) for the DP table and O(n) for the prefix XOR array.

Solution

We precompute a DP table where dp[i][j] holds the maximum XOR score among all subarrays within the segment nums[i..j]. First, we build a prefix XOR array (P) such that P[k] is the XOR of nums[0] to nums[k-1]. The XOR of any subarray nums[i..j] is then P[i] XOR P[j+1]. For every subarray:

  • If the subarray contains only one element (i.e. i == j), the score is simply nums[i].
  • If the subarray length (j - i + 1) is even, its score is the XOR of all its elements.
  • If the subarray length is odd and greater than 1, its score is nums[i] XOR nums[j]. We then update dp[i][j] as the maximum of:   • dp[i][j-1] (the best score in nums[i..j-1]),   • dp[i+1][j] (the best score in nums[i+1..j]), and   • the score for the subarray nums[i..j]. After this precomputation, each query [l, r] is answered in O(1) time by returning dp[l][r].

Code Solutions

# Python solution with line-by-line comments
def maximumXorScoreSubarrayQueries(nums, queries):
    n = len(nums)
    # Build prefix XOR array where prefix[i] is XOR of nums[0...i-1]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] ^ nums[i]

    # Initialize DP table. dp[i][j] stores max XOR score in subarray nums[i..j].
    dp = [[0] * n for _ in range(n)]
    
    # Base case: every single element subarray
    for i in range(n):
        dp[i][i] = nums[i]

    # Process subarrays of length >= 2
    for length in range(2, n + 1):  # length from 2 to n
        for i in range(n - length + 1):
            j = i + length - 1
            # Depending on whether the subarray length is even or odd:
            if length % 2 == 0:
                # Even length: XOR of all elements from i to j
                current_score = prefix[j + 1] ^ prefix[i]
            else:
                # Odd length (>=3): score is XOR of first and last element
                current_score = nums[i] ^ nums[j]
            # dp[i][j] is the maximum of:
            # - best in subarray excluding the last element,
            # - best in subarray excluding the first element,
            # - the current subarray's score.
            dp[i][j] = max(dp[i][j-1], dp[i+1][j], current_score)
    
    # Answer each query using precomputed DP table
    results = []
    for l, r in queries:
        results.append(dp[l][r])
    return results

# Example usage:
nums = [2,8,4,32,16,1]
queries = [[0,2],[1,4],[0,5]]
print(maximumXorScoreSubarrayQueries(nums, queries))
← Back to All Questions