Skip to main content

1310. XOR Queries of a Subarray

medium

Answer many subarray-XOR queries quickly. The prefix-XOR trick mirrors prefix-sum: precompute once, then every range is XOR of two endpoints.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an array arr of positive integers and an array queries where queries[i] = [left_i, right_i]. For each query i compute the XOR of elements from left_i to right_i (that is, arr[left_i] XOR arr[left_i + 1] XOR ... XOR arr[right_i]). Return an array answer where answer[i] is the answer to the ith query.

Constraints

  • 1 <= arr.length, queries.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • queries[i].length == 2
  • 0 <= left_i <= right_i < arr.length

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive per-query XOR is O(n) per query, O(n * q) total. With 9 * 10^8 worst case that's TLE.

Hint 2

Prefix-XOR is the bitwise analog of prefix-sum. Let p[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] with p[0] = 0.

Hint 3

Then XOR of arr[l..r] = p[r+1] ^ p[l]. Each query is now O(1).

Solution approach

Reveal approach

Prefix-XOR table. Build p of length n + 1 with p[0] = 0 and p[i + 1] = p[i] ^ arr[i]. For each query [l, r], append p[r + 1] ^ p[l] to the answer list. Why this works: XOR is its own inverse, so XOR'ing prefix p[r + 1] (which includes arr[0..r]) with prefix p[l] (which includes arr[0..l-1]) cancels the shared front portion, leaving arr[l..r]. Build phase O(n), query phase O(1) per query, total O(n + q) time. O(n) extra space for the prefix table.

Complexity

Time
O(n + q)
Space
O(n)

Related patterns

  • bit-manipulation
  • prefix-sum
  • xor

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill XOR Queries of a Subarray and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →