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
XOR Queries: arr = [1,3,4,8], query = [1,2]Original Array:13480123Prefix XOR:012614Query [1,2]: prefix[3] ⊕ prefix[1] = 6 ⊕ 1 = 7Result: 7
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
Asked in
Amazon 15 Microsoft 12 Google 8 Facebook 6
28.5K Views
Medium Frequency
~15 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen