XOR Queries of a Subarray - Problem
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.
Input & Output
Example 1 — Basic XOR Queries
$
Input:
arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
›
Output:
[2,7,14,8]
💡 Note:
Query [0,1]: 1⊕3=2, Query [1,2]: 3⊕4=7, Query [0,3]: 1⊕3⊕4⊕8=14, Query [3,3]: 8
Example 2 — Single Element Array
$
Input:
arr = [4], queries = [[0,0]]
›
Output:
[4]
💡 Note:
Only one element, so XOR of range [0,0] is just arr[0] = 4
Example 3 — Full Array Range
$
Input:
arr = [16,8,4,2], queries = [[0,3]]
›
Output:
[30]
💡 Note:
XOR of entire array: 16⊕8⊕4⊕2 = 30
Constraints
- 1 ≤ arr.length ≤ 3 × 104
- 1 ≤ arr[i] ≤ 109
- 1 ≤ queries.length ≤ 3 × 104
- queries[i].length == 2
- 0 ≤ lefti ≤ righti < arr.length
Visualization
Tap to expand
Understanding the Visualization
1
Input
Array and list of range queries
2
Prefix XOR
Build cumulative XOR array
3
Query Answer
Use prefix XOR to get range result
Key Takeaway
🎯 Key Insight: XOR prefix sums enable O(1) range queries using the cancellation property
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code