#1310

Medium

LeetCode Problem Workspace

XOR Queries of a Subarray

Compute XOR results for multiple subarray queries using efficient prefix XOR to reduce repeated computation overhead in arrays.

array bit manipulation prefix sum

Problem Statement

Given an array of positive integers and a list of queries where each query specifies a range [left, right], compute the XOR of all elements within that range for each query. Return the results as an array corresponding to the queries in order.

Each query can cover any contiguous segment of the array, and the solution must efficiently handle large arrays and many queries by leveraging properties of XOR and prefix calculations to minimize repeated operations.

Examples

Example 1

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]

Output: [2,7,14,8]

The binary representation of the elements in the array are: 1 = 0001 3 = 0011 4 = 0100 8 = 1000 The XOR values for queries are: [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8

Example 2

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]

Output: [8,0,4,4]

Example details omitted.

Constraints

1 <= arr.length, queries.length <= 3 * 104
1 <= arr[i] <= 109
queries[i].length == 2
0 <= lefti <= righti < arr.length

Solution Approach

Compute Prefix XOR Array

Build a prefix XOR array where prefix[i] stores the XOR of elements from arr[0] to arr[i-1]. This allows O(1) subarray XOR computation using the property x ^ x = 0 and prefix[right+1] ^ prefix[left].

Answer Queries in Constant Time

For each query [left, right], return prefix[right+1] ^ prefix[left]. This uses the prefix XOR array to directly compute the subarray XOR without iterating over elements, handling overlapping queries efficiently.

Handle Edge Cases and Constraints

Ensure the prefix array is initialized with 0 at index 0 to handle queries starting at index 0. Validate queries are within array bounds and leverage the property of XOR to avoid recomputation even for large arrays.

Complexity Analysis

Metric	Value
Time	O(n + q)
Space	O(1)

Time complexity is O(n + q), where n is array length and q is number of queries, because building the prefix array takes O(n) and each query is answered in O(1). Space complexity is O(n) for the prefix XOR array, but additional space for output is negligible.

What Interviewers Usually Probe

Check if you recognize that XOR has an inverse property that allows prefix computations.
They might ask for an optimization beyond naive O(n*q) subarray calculation.
Expect a hint about building cumulative data structures, specifically prefix XOR, for constant-time queries.

Common Pitfalls or Variants

Common pitfalls

Not initializing prefix array with zero leading to incorrect XOR for subarrays starting at index 0.
Attempting to iterate over the subarray for each query, resulting in TLE for large inputs.
Misunderstanding XOR properties, especially forgetting that x ^ x = 0 can simplify calculations.

Follow-up variants

Compute XOR for dynamic ranges where elements are updated between queries.
Use XOR queries on a 2D matrix instead of a 1D array, applying similar prefix ideas.
Determine the maximum XOR among all subarray ranges instead of specific queries.

FAQ

What is the most efficient way to solve XOR Queries of a Subarray?

Use a prefix XOR array so each query is answered in constant time by computing prefix[right+1] ^ prefix[left].

Why use prefix XOR instead of iterating each subarray?

Iterating each subarray results in O(n*q) complexity which is too slow; prefix XOR reduces each query to O(1).

How does XOR property x ^ x = 0 help in this problem?

It allows the cancellation of overlapping elements in prefix XOR, enabling fast subarray computation without recomputation.

Can this approach handle large arrays and many queries?

Yes, because building the prefix array is O(n) and each query is O(1), making it scalable for arrays up to 3*10^4 elements.

Is there a variant for 2D arrays?

Yes, prefix XOR can be extended to 2D matrices, computing submatrix XOR using similar cancellation principles.

terminal

Solution

Solution 1: Prefix XOR

We can use a prefix XOR array $s$ of length $n+1$ to store the prefix XOR results of the array $\textit{arr}$, where $s[i] = s[i-1] \oplus \textit{arr}[i-1]$. That is, $s[i]$ represents the XOR result of the first $i$ elements of $\textit{arr}$.

1

2

3

4

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        s = list(accumulate(arr, xor, initial=0))
        return [s[r + 1] ^ s[l] for l, r in queries]

Continue Practicing

#1442 count triplets that can form two arrays of equal xor #1177 can make palindrome from substring #995 minimum number of k consecutive bit flips