Get started

XOR Queries of a Subarray — Medium Problem & Solution

For each query [left, right], compute the XOR of arr[left] … arr[right] inclusive. Return the answers in query order.

Problem statement

For each query [left, right], compute the XOR of arr[left] … arr[right] inclusive.

Return the answers in query order.

Example 1

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation: 1 XOR 3 = 2, 3 XOR 4 = 7, all four XOR to 14, and the last element alone is 8.

Example 2

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

Example 3

Input: arr = [5], queries = [[0,0]]
Output: [5]

Constraints

  • 1 <= arr.length <= 30000
  • 1 <= queries.length <= 30000
  • 0 <= left <= right < arr.length
  • 1 <= arr[i] <= 1000000000

How to solve XOR Queries of a Subarray

XOR has the same telescoping property as addition, with XOR playing the role of both plus and minus. So a prefix-XOR array answers any range in constant time.

Approach

  1. Build pref of length n + 1 with pref[0] = 0 and pref[i+1] = pref[i] ^ arr[i].
  2. For a query [l, r], return pref[r + 1] ^ pref[l].

Why it works

pref[r+1] = arr[0] ^ … ^ arr[r] and pref[l] = arr[0] ^ … ^ arr[l-1]. XOR-ing them cancels the shared prefix, because every element in it appears twice and x ^ x = 0, leaving exactly arr[l] ^ … ^ arr[r].

Complexity

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

Pitfalls

  • Off-by-one: the range ends at r inclusive, so the prefix index is r + 1.
  • Using subtraction instead of XOR breaks the cancellation.

Reference solution

Python

from typing import List

def xorQueries(arr: List[int], queries: List[List[int]]) -> List[int]:
    pref = [0]
    for x in arr:
        pref.append(pref[-1] ^ x)
    return [pref[r + 1] ^ pref[l] for l, r in queries]

JavaScript

var xorQueries = function(arr, queries) {
    var pref = [0];
    for (var i = 0; i < arr.length; i++) pref.push(pref[i] ^ arr[i]);
    var out = [];
    for (var j = 0; j < queries.length; j++) {
        out.push(pref[queries[j][1] + 1] ^ pref[queries[j][0]]);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue