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

XOR Queries of a Subarray

Number: 1435

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Airtel

Problem Description

Given an array of positive integers arr and a 2D array queries where each query is represented as [left, right], compute the XOR of the subarray elements from index left to right (inclusive) for each query. Return the results as an array.

Key Insights

  • Precompute a prefix XOR array where prefixXOR[i] represents the XOR of all elements from arr[0] to arr[i-1].
  • The XOR for any subarray [left, right] can be computed in constant time as prefixXOR[right+1] XOR prefixXOR[left].
  • This reduces the overall time complexity of processing queries to O(1) per query.

Space and Time Complexity

Time Complexity: O(n + q), where n is the length of arr and q is the number of queries. Space Complexity: O(n) for the prefix XOR array.

Solution

The solution utilizes a prefix XOR technique. First, compute a prefixXOR array where each entry holds the cumulative XOR up to that point. For any given query [L, R], the XOR of the subarray is computed using the relationship:   subarray XOR = prefixXOR[R + 1] XOR prefixXOR[L]. This method allows each query to be answered in constant time, after an initial O(n) preprocessing step.

Code Solutions

# Python solution using prefix XOR

def xorQueries(arr, queries):
    # Precompute prefix XOR array with the initial value 0
    prefix_xor = [0]
    for num in arr:
        # Append cumulative XOR up to current element
        prefix_xor.append(prefix_xor[-1] ^ num)
    
    results = []  # To store the result for each query
    # Compute XOR for each query using the prefix XOR values
    for left, right in queries:
        # XOR of subarray [left, right] = prefix_xor[right + 1] XOR prefix_xor[left]
        results.append(prefix_xor[right + 1] ^ prefix_xor[left])
    
    return results

# Example usage:
arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
print(xorQueries(arr, queries))  # Expected output: [2, 7, 14, 8]
← Back to All Questions