XOR Queries of a Subarray

Medium
734.

XOR Queries of a Subarray

XOR Queries of a Subarray is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number[][]} queries
 * @return {number[]}
 */
var xorQueries = function(arr, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

XOR Queries of a Subarray — Solution in Python, Java & C++

XOR Queries of a Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

XOR Queries of a Subarray is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google and Adobe interviews.

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

Hints for XOR Queries of a Subarray

  1. Hint 1

    Answering each query with its own loop is O(n) per query, which is too slow.

  2. Hint 2

    Build prefix XORs: pref[i] is the XOR of the first i elements.

  3. Hint 3

    Then the range XOR is pref[right + 1] XOR pref[left], because the shared prefix cancels.

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]

Java

public static int[] xorQueries(int[] arr, int[][] queries) {
    int n = arr.length;
    int[] pref = new int[n + 1];
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] ^ arr[i];
    int[] out = new int[queries.length];
    for (int j = 0; j < queries.length; j++) {
        out[j] = pref[queries[j][1] + 1] ^ pref[queries[j][0]];
    }
    return out;
}

C++

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
    int n = (int) arr.size();
    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] ^ arr[i];
    vector<int> out;
    for (auto& q : queries) out.push_back(pref[q[1] + 1] ^ pref[q[0]]);
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation