You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].
For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).
Return an array answer where answer[i] is the answer to the ith query.
Example 1:
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] Output: [2,7,14,8] Explanation: 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]
Constraints:
1 <= arr.length, queries.length <= 3 * 1041 <= arr[i] <= 109queries[i].length == 20 <= lefti <= righti < arr.lengthProblem Overview: You receive an integer array and multiple queries. Each query contains two indices [L, R], and you must return the XOR of all elements between those indices (inclusive). Computing the XOR repeatedly for many queries becomes expensive without preprocessing.
Approach 1: Brute Force Iteration (Time: O(q * n), Space: O(1))
The straightforward method processes each query independently. For a query [L, R], iterate from index L to R and accumulate the result using the XOR operator. Since XOR is associative, you simply apply result ^= arr[i] for every element in the range. This approach is easy to implement and works well when the number of queries is small. However, if the array is large or there are many queries, repeatedly scanning subarrays becomes inefficient. In the worst case, each query touches nearly the entire array, resulting in O(q * n) time complexity.
Approach 2: Prefix XOR (Time: O(n + q), Space: O(n))
The optimal strategy preprocesses the array using a prefix XOR array. Similar to prefix sums, you build an array where prefix[i] stores the XOR of elements from index 0 to i. The key property of XOR makes range queries efficient: XOR(L..R) = prefix[R] ^ prefix[L-1]. If L is zero, the result is simply prefix[R]. This works because XORing the same value twice cancels it out. After computing the prefix array in a single pass, every query is answered in constant time with just two XOR operations.
This method turns repeated subarray computations into simple lookups. Preprocessing takes O(n), and handling q queries takes O(q). The approach is widely used in problems involving repeated range operations on arrays, especially when XOR or addition properties allow efficient cancellation.
The technique relies heavily on concepts from Array traversal, Bit Manipulation, and the classic Prefix Sum pattern. Once you recognize that XOR behaves similarly to addition under prefix preprocessing, the problem reduces to constant-time query evaluation.
Recommended for interviews: The Prefix XOR approach is what interviewers expect. It demonstrates recognition of prefix preprocessing patterns and understanding of XOR properties. Mentioning the brute force method first shows you understand the baseline solution, but moving to prefix XOR proves you can optimize repeated range queries from linear time to constant time.
This approach involves directly computing the XOR for each range specified in the queries. For each query, iterate over the specified subarray range and compute the XOR.
This C implementation uses a nested loop for each query. The outer loop iterates through each query, and the inner loop computes the XOR from the left index to the right index of each query, storing the result in the output array.
Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries.
Space Complexity: O(q) for storing the query results.
To optimize the XOR computation, we can use a prefix XOR array. Compute the XOR of all elements up to each position in the array. Then to find the XOR for a range simply subtract the prefix value before the start of the range from the prefix at the end of the range.
This C implementation computes the prefix XOR array, which is then used to quickly compute the XOR for any subrange as the difference between the prefix XOR at right + 1 and left indices.
Time Complexity: O(n + q), where n is the number of elements and q is the number of queries.
Space Complexity: O(n) for the prefix XOR array.
We can use a prefix XOR array s of length n+1 to store the prefix XOR results of the array arr, where s[i] = s[i-1] \oplus arr[i-1]. That is, s[i] represents the XOR result of the first i elements of arr.
For a query [l, r], we can obtain:
$
\begin{aligned}
arr[l] \oplus arr[l+1] \oplus cdots \oplus arr[r] &= (arr[0] \oplus arr[1] \oplus cdots \oplus arr[l-1]) \oplus (arr[0] \oplus arr[1] \oplus cdots \oplus arr[r]) \
&= s[l] \oplus s[r+1]
\end{aligned}
Time complexity is O(n+m), and space complexity is O(n). Here, n and m are the lengths of the array arr and the query array queries$, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries. |
| Optimized Prefix XOR Approach | Time Complexity: O(n + q), where n is the number of elements and q is the number of queries. |
| Prefix XOR | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(q * n) | O(1) | When queries are very few or the array size is small and preprocessing is unnecessary |
| Prefix XOR | O(n + q) | O(n) | Best choice for multiple range XOR queries; preprocess once and answer each query in constant time |
XOR Queries of a Subarray | Simple Explanation | Leetcode 1310 | codestorywithMIK • codestorywithMIK • 8,691 views views
Watch 9 more video solutions →Practice XOR Queries of a Subarray with our built-in code editor and test cases.
Practice on FleetCode