1310. XOR Queries of a Subarray - Solution

Q: Is XOR Queries of a Subarray easy or hard?

The problem is rated Medium because the brute force solution is straightforward, but recognizing the prefix XOR optimization requires understanding of XOR cancellation properties and prefix preprocessing techniques.

Q: XOR Queries of a Subarray Python/Java solution

The optimal solution in Python or Java builds a prefix XOR array and processes queries using prefix[R] ^ prefix[L-1]. The preprocessing step runs in O(n), and each query runs in O(1), making it efficient for large inputs.

Q: How to solve XOR Queries of a Subarray in O(n)?

Precompute a prefix XOR array in O(n). For each index i, store prefix[i] = prefix[i-1] ^ arr[i]. Then answer each query [L, R] using prefix[R] ^ prefix[L-1]. This allows constant-time query processing after linear preprocessing.

Q: What is the best approach for XOR Queries of a Subarray?

The Prefix XOR approach is the most efficient. Build a prefix array where prefix[i] stores XOR of elements from index 0 to i. Each query [L, R] can then be answered in O(1) using prefix[R] ^ prefix[L-1], giving an overall complexity of O(n + q).

Q: Is XOR Queries of a Subarray asked at Google/Amazon/Meta?

Problems involving prefix XOR and range query preprocessing commonly appear in interviews at companies like Amazon, Google, and Meta. Variations often test understanding of prefix sums, XOR properties, and efficient query handling.

Q: What data structure is used in XOR Queries of a Subarray?

The solution primarily uses an array to store prefix XOR values. This preprocessing structure allows constant-time lookup for any subarray XOR query.

Q: What is the time complexity of XOR Queries of a Subarray?

The brute force approach takes O(q * n) time because each query may scan the subarray. Using the Prefix XOR technique reduces this to O(n + q), where n is the array size and q is the number of queries.

The problem

You are given an array arr of positive integers. You are also given the 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 i^th query.

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]

Constraints:

1 <= arr.length, queries.length <= 3 * 10⁴
1 <= arr[i] <= 10⁹
queries[i].length == 2
0 <= left_i <= right_i < arr.length

Approach overview

Problem Overview: You receive an integer array and multiple queries. Each query contains two indices [L, R], and you must return the XOR of all elements between those indices (inclusive). Computing the XOR repeatedly for many queries becomes expensive without preprocessing.

Approach 1: Brute Force Iteration (Time: O(q * n), Space: O(1))

The straightforward method processes each query independently. For a query [L, R], iterate from index L to R and accumulate the result using the XOR operator. Since XOR is associative, you simply apply result ^= arr[i] for every element in the range. This approach is easy to implement and works well when the number of queries is small. However, if the array is large or there are many queries, repeatedly scanning subarrays becomes inefficient. In the worst case, each query touches nearly the entire array, resulting in O(q * n) time complexity.

Approach 2: Prefix XOR (Time: O(n + q), Space: O(n))

The optimal strategy preprocesses the array using a prefix XOR array. Similar to prefix sums, you build an array where prefix[i] stores the XOR of elements from index 0 to i. The key property of XOR makes range queries efficient: XOR(L..R) = prefix[R] ^ prefix[L-1]. If L is zero, the result is simply prefix[R]. This works because XORing the same value twice cancels it out. After computing the prefix array in a single pass, every query is answered in constant time with just two XOR operations.

This method turns repeated subarray computations into simple lookups. Preprocessing takes O(n), and handling q queries takes O(q). The approach is widely used in problems involving repeated range operations on arrays, especially when XOR or addition properties allow efficient cancellation.

The technique relies heavily on concepts from Array traversal, Bit Manipulation, and the classic Prefix Sum pattern. Once you recognize that XOR behaves similarly to addition under prefix preprocessing, the problem reduces to constant-time query evaluation.

Recommended for interviews: The Prefix XOR approach is what interviewers expect. It demonstrates recognition of prefix preprocessing patterns and understanding of XOR properties. Mentioning the brute force method first shows you understand the baseline solution, but moving to prefix XOR proves you can optimize repeated range queries from linear time to constant time.

Approach 1: Brute Force Approach

This approach involves directly computing the XOR for each range specified in the queries. For each query, iterate over the specified subarray range and compute the XOR.

Python

def xorQueries(arr, queries):
    result = []
    for q in queries:
        xor_result = 0
        for i in range(q[0], q[1] + 1):
            xor_result ^= arr[i]
        result.append(xor_result)
    return result

arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
print(xorQueries(arr, queries))

Java

import java.util.*;

public class XorQueries {
    public static int[] xorQueries(int[] arr, int[][] queries) {
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int xor_result = 0;
            for (int j = queries[i][0]; j <= queries[i][1]; j++) {
                xor_result ^= arr[j];
            }
            result[i] = xor_result;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 8};
        int[][] queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
        int[] result = xorQueries(arr, queries);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <vector>

std::vector<int> xorQueries(std::vector<int> &arr, std::vector<std::vector<int>> &queries) {
    std::vector<int> result;
    for (const auto &query : queries) {
        int xor_result = 0;
        for (int i = query[0]; i <= query[1]; ++i) {
            xor_result ^= arr[i];
        }
        result.push_back(xor_result);
    }
    return result;
}

int main() {
    std::vector<int> arr = {1, 3, 4, 8};
    std::vector<std::vector<int>> queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
    std::vector<int> result = xorQueries(arr, queries);
    for (int res : result) {
        std::cout << res << " ";
    }
    return 0;
}

JavaScript

function xorQueries(arr, queries) {
    let result = [];
    for (let q of queries) {
        let xor_result = 0;
        for (let i = q[0]; i <= q[1]; i++) {
            xor_result ^= arr[i];
        }
        result.push(xor_result);
    }
    return result;
}

const arr = [1, 3, 4, 8];
const queries = [[0, 1], [1, 2], [0, 3], [3, 3]];
console.log(xorQueries(arr, queries));

#include <stdio.h>
#include <stdlib.h>

int *xorQueries(int *arr, int arrSize, int **queries, int queriesSize, int *queriesColSize, int *returnSize) {
    *returnSize = queriesSize;
    int *result = (int *)malloc(sizeof(int) * queriesSize);
    
    for (int i = 0; i < queriesSize; i++) {
        int left = queries[i][0], right = queries[i][1];
        int xor_result = 0;
        for (int j = left; j <= right; j++) {
            xor_result ^= arr[j];
        }
        result[i] = xor_result;
    }
    return result;
}

int main() {
    int arr[] = {1, 3, 4, 8};
    int arrSize = 4;
    int queries[][2] = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
    int queriesSize = 4;
    int queriesColSize[] = {2, 2, 2, 2};
    int *resultSize = (int *)malloc(sizeof(int));
    int **queriesPointer = (int **)malloc(queriesSize * sizeof(int *));
    for (int i = 0; i < queriesSize; i++) {
        queriesPointer[i] = queries[i];
    }
    int *result = xorQueries(arr, arrSize, queriesPointer, queriesSize, queriesColSize, resultSize);
    for (int i = 0; i < *resultSize; i++) {
        printf("%d ", result[i]);
    }
    free(resultSize);
    free(result);
    free(queriesPointer);
    return 0;
}

using System;
using System.Collections.Generic;

class XorQueries {
    public static int[] XorQueries(int[] arr, int[][] queries) {
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int xor_result = 0;
            for (int j = queries[i][0]; j <= queries[i][1]; j++) {
                xor_result ^= arr[j];
            }
            result[i] = xor_result;
        }
        return result;
    }

    static void Main() {
        int[] arr = {1, 3, 4, 8};
        int[][] queries = new int[][] {
            new int[] {0, 1},
            new int[] {1, 2},
            new int[] {0, 3},
            new int[] {3, 3}
        };
        int[] result = XorQueries(arr, queries);
        Console.WriteLine(string.Join(" ", result));
    }
}

This Python function iterates over each query and computes the XOR over the specified subarray, appending the result to a list, which is returned at the end.

Complexity

Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries.
Space Complexity: O(q).

Try this approach in the editor

Approach 2: Optimized Prefix XOR Approach

To optimize the XOR computation, we can use a prefix XOR array. Compute the XOR of all elements up to each position in the array. Then to find the XOR for a range simply subtract the prefix value before the start of the range from the prefix at the end of the range.

Python

def xorQueries(arr, queries):
    prefixXor = [0] * (len(arr) + 1)
    for i in range(1, len(arr) + 1):
        prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1]
    result = []
    for left, right in queries:
        result.append(prefixXor[right + 1] ^ prefixXor[left])
    return result

arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
print(xorQueries(arr, queries))

Java

import java.util.*;

public class XorQueries {
    public static int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] prefixXor = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
        }
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            result[i] = prefixXor[queries[i][1] + 1] ^ prefixXor[queries[i][0]];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 8};
        int[][] queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
        int[] result = xorQueries(arr, queries);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <vector>

std::vector<int> xorQueries(std::vector<int>& arr, std::vector<std::vector<int>>& queries) {
    int n = arr.size();
    std::vector<int> prefixXor(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
    }
    std::vector<int> result;
    for (const auto& query : queries) {
        result.push_back(prefixXor[query[1] + 1] ^ prefixXor[query[0]]);
    }
    return result;
}

int main() {
    std::vector<int> arr = {1, 3, 4, 8};
    std::vector<std::vector<int>> queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
    std::vector<int> result = xorQueries(arr, queries);
    for (int res : result) {
        std::cout << res << " ";
    }
    return 0;
}

JavaScript

function xorQueries(arr, queries) {
    const prefixXor = new Array(arr.length + 1).fill(0);
    for (let i = 1; i <= arr.length; i++) {
        prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
    }
    const result = [];
    queries.forEach(([left, right]) => {
        result.push(prefixXor[right + 1] ^ prefixXor[left]);
    });
    return result;
}

const arr = [1, 3, 4, 8];
const queries = [[0, 1], [1, 2], [0, 3], [3, 3]];
console.log(xorQueries(arr, queries));

#include <stdio.h>
#include <stdlib.h>

int *xorQueries(int *arr, int arrSize, int **queries, int queriesSize, int *queriesColSize, int *returnSize) {
    *returnSize = queriesSize;
    int *result = (int *)malloc(sizeof(int) * queriesSize);
    int *prefixXor = (int *)malloc(sizeof(int) * (arrSize + 1));

    prefixXor[0] = 0;
    for (int i = 1; i <= arrSize; i++) {
        prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
    }

    for (int i = 0; i < queriesSize; i++) {
        int left = queries[i][0], right = queries[i][1];
        result[i] = prefixXor[right + 1] ^ prefixXor[left];
    }
    free(prefixXor);
    return result;
}

int main() {
    int arr[] = {1, 3, 4, 8};
    int arrSize = 4;
    int queries[][2] = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
    int queriesSize = 4;
    int queriesColSize[] = {2, 2, 2, 2};
    int *resultSize = (int *)malloc(sizeof(int));
    int **queriesPointer = (int **)malloc(queriesSize * sizeof(int *));
    for (int i = 0; i < queriesSize; i++) {
        queriesPointer[i] = queries[i];
    }
    int *result = xorQueries(arr, arrSize, queriesPointer, queriesSize, queriesColSize, resultSize);
    for (int i = 0; i < *resultSize; i++) {
        printf("%d ", result[i]);
    }
    free(resultSize);
    free(result);
    free(queriesPointer);
    return 0;
}

using System;

class XorQueries {
    public static int[] XorQueries(int[] arr, int[][] queries) {
        int n = arr.Length;
        int[] prefixXor = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
        }
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            result[i] = prefixXor[queries[i][1] + 1] ^ prefixXor[queries[i][0]];
        }
        return result;
    }

    static void Main() {
        int[] arr = {1, 3, 4, 8};
        int[][] queries = new int[][] {
            new int[] {0, 1},
            new int[] {1, 2},
            new int[] {0, 3},
            new int[] {3, 3}
        };
        int[] result = XorQueries(arr, queries);
        Console.WriteLine(string.Join(" ", result));
    }
}

In Python, this function calculates the prefix XOR array to allow constant time calculation of the XOR for any subarray. It then efficiently computes the result for each query.

Complexity

Time Complexity: O(n + q), where n is the number of elements and q is the number of queries.
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Prefix XOR

We can use a prefix XOR array s of length n+1 to store the prefix XOR results of the array arr, where s[i] = s[i-1] \oplus arr[i-1]. That is, s[i] represents the XOR result of the first i elements of arr.

For a query [l, r], we can obtain:

$\begin{aligned} arr[l] \oplus arr[l+1] \oplus cdots \oplus arr[r] &= (arr[0] \oplus arr[1] \oplus cdots \oplus arr[l-1]) \oplus (arr[0] \oplus arr[1] \oplus cdots \oplus arr[r]) \ &= s[l] \oplus s[r+1] \end{aligned}

Time complexity is O(n+m), and space complexity is O(n). Here, n and m are the lengths of the array arr and the query array queries$, respectively.

TypeScript

function xorQueries(arr: number[], queries: number[][]): number[] {
    const n = arr.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] ^ arr[i];
    }
    return queries.map(([l, r]) => s[r + 1] ^ s[l]);
}

func xorQueries(arr []int, queries [][]int) (ans []int) {
	n := len(arr)
	s := make([]int, n+1)
	for i, x := range arr {
		s[i+1] = s[i] ^ x
	}
	for _, q := range queries {
		l, r := q[0], q[1]
		ans = append(ans, s[r+1]^s[l])
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries. Space Complexity: O(q).
Optimized Prefix XOR Approach	Time Complexity: O(n + q), where n is the number of elements and q is the number of queries. Space Complexity: O(n).
Prefix XOR	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Iteration	O(q * n)	O(1)	When queries are very few or the array size is small and preprocessing is unnecessary
Prefix XOR	O(n + q)	O(n)	Best choice for multiple range XOR queries; preprocess once and answer each query in constant time

Frequently asked questions

Is XOR Queries of a Subarray easy or hard?

The problem is rated Medium because the brute force solution is straightforward, but recognizing the prefix XOR optimization requires understanding of XOR cancellation properties and prefix preprocessing techniques.

XOR Queries of a Subarray Python/Java solution

The optimal solution in Python or Java builds a prefix XOR array and processes queries using prefix[R] ^ prefix[L-1]. The preprocessing step runs in O(n), and each query runs in O(1), making it efficient for large inputs.

How to solve XOR Queries of a Subarray in O(n)?

Precompute a prefix XOR array in O(n). For each index i, store prefix[i] = prefix[i-1] ^ arr[i]. Then answer each query [L, R] using prefix[R] ^ prefix[L-1]. This allows constant-time query processing after linear preprocessing.

What is the best approach for XOR Queries of a Subarray?

The Prefix XOR approach is the most efficient. Build a prefix array where prefix[i] stores XOR of elements from index 0 to i. Each query [L, R] can then be answered in O(1) using prefix[R] ^ prefix[L-1], giving an overall complexity of O(n + q).

Is XOR Queries of a Subarray asked at Google/Amazon/Meta?

Problems involving prefix XOR and range query preprocessing commonly appear in interviews at companies like Amazon, Google, and Meta. Variations often test understanding of prefix sums, XOR properties, and efficient query handling.

What data structure is used in XOR Queries of a Subarray?

The solution primarily uses an array to store prefix XOR values. This preprocessing structure allows constant-time lookup for any subarray XOR query.

What is the time complexity of XOR Queries of a Subarray?

The brute force approach takes O(q * n) time because each query may scan the subarray. Using the Prefix XOR technique reduces this to O(n + q), where n is the array size and q is the number of queries.

XOR Queries of a Subarray solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Prefix XOR Approach

Approach 3: Prefix XOR

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

XOR Queries of a Subarray solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Prefix XOR Approach

Approach 3: Prefix XOR

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems