Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

XOR Queries of a Subarray

MEDIUMProblemSolveExternal Links

Description

You are given an array arr of positive integers. You are also given an array queries where queries[i] = [left_i, right_i].

For each query i, compute the XOR of elements from index left_i to right_i (inclusive):

arr[left_i] XOR arr[left_i + 1] XOR ... XOR arr[right_i]

Return an array answer where answer[i] is the result of the i-th query.

Recall: The XOR operation (^) returns 1 when the corresponding bits differ and 0 when they match. XOR is associative (a ^ (b ^ c) = (a ^ b) ^ c), commutative (a ^ b = b ^ a), and self-inverse (a ^ a = 0). These properties are key to building an efficient solution.

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 representations: 1 = 0001, 3 = 0011, 4 = 0100, 8 = 1000
  • Query [0,1]: 1 XOR 3 = 0001 XOR 0011 = 0010 = 2
  • Query [1,2]: 3 XOR 4 = 0011 XOR 0100 = 0111 = 7
  • Query [0,3]: 1 XOR 3 XOR 4 XOR 8 = 0001 XOR 0011 XOR 0100 XOR 1000 = 1110 = 14
  • Query [3,3]: 8 = 8 (single element, no XOR needed)

Example 2

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

Output: [8, 0, 4, 4]

Explanation:

  • Query [2,3]: 2 XOR 10 = 0010 XOR 1010 = 1000 = 8
  • Query [1,3]: 8 XOR 2 XOR 10 = 1000 XOR 0010 XOR 1010 = 0000 = 0
  • Query [0,0]: 4 = 4 (single element)
  • Query [0,3]: 4 XOR 8 XOR 2 XOR 10 = 0100 XOR 1000 XOR 0010 XOR 1010 = 0100 = 4

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

Editorial

Brute Force - Iterate for Each Query

Intuition

The most straightforward approach is to directly compute the XOR for each query. For every query [left, right], we iterate through the subarray from index left to right, XOR-ing all elements together.

Think of it like being asked to sum a section of a receipt multiple times. Each time someone asks "what's the total from line 3 to line 7?", you physically run your finger down those lines and add them up. If someone then asks "what's the total from line 1 to line 10?", you start over and scan again from scratch.

This works, but if you have many queries and the array is large, you're doing a lot of redundant work — re-reading the same elements over and over for overlapping ranges.

Step-by-Step Explanation

Let's trace through arr = [1, 3, 4, 8], queries = [[0,1], [1,2], [0,3], [3,3]]:

Query 1: [0, 1]

  • Start with result = 0
  • XOR with arr[0] = 1: result = 0 ^ 1 = 1
  • XOR with arr[1] = 3: result = 1 ^ 3 = 2
  • Answer: 2

Query 2: [1, 2]

  • Start with result = 0
  • XOR with arr[1] = 3: result = 0 ^ 3 = 3
  • XOR with arr[2] = 4: result = 3 ^ 4 = 7
  • Answer: 7

Query 3: [0, 3]

  • Start with result = 0
  • XOR with arr[0] = 1: result = 0 ^ 1 = 1
  • XOR with arr[1] = 3: result = 1 ^ 3 = 2
  • XOR with arr[2] = 4: result = 2 ^ 4 = 6
  • XOR with arr[3] = 8: result = 6 ^ 8 = 14
  • Answer: 14

Query 4: [3, 3]

  • Start with result = 0
  • XOR with arr[3] = 8: result = 0 ^ 8 = 8
  • Answer: 8

Final output: [2, 7, 14, 8]

Brute Force: Processing Query [0, 3] on arr = [1, 3, 4, 8] — Watch how the brute force approach iterates through every element in the query range, XOR-ing them one by one to accumulate the result.

Algorithm

  1. Initialize an empty result array answer
  2. For each query [left, right] in queries:
    • Initialize xor_val = 0
    • For i from left to right:
      • xor_val = xor_val ^ arr[i]
    • Append xor_val to answer
  3. Return answer

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> answer;
        
        for (auto& query : queries) {
            int left = query[0];
            int right = query[1];
            int xorVal = 0;
            
            // XOR all elements from left to right
            for (int i = left; i <= right; i++) {
                xorVal ^= arr[i];
            }
            
            answer.push_back(xorVal);
        }
        
        return answer;
    }
};
from typing import List

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        answer = []
        
        for left, right in queries:
            xor_val = 0
            
            # XOR all elements from left to right
            for i in range(left, right + 1):
                xor_val ^= arr[i]
            
            answer.append(xor_val)
        
        return answer
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int[] answer = new int[queries.length];
        
        for (int q = 0; q < queries.length; q++) {
            int left = queries[q][0];
            int right = queries[q][1];
            int xorVal = 0;
            
            // XOR all elements from left to right
            for (int i = left; i <= right; i++) {
                xorVal ^= arr[i];
            }
            
            answer[q] = xorVal;
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n × q)

For each of the q queries, we potentially iterate through up to n elements of the array. In the worst case (every query asks for the XOR of the entire array), we do n operations per query, giving O(n × q) total. With n = q = 3 × 10⁴, this is up to 9 × 10⁸ operations — likely too slow.

Space Complexity: O(1) auxiliary

We only use a few integer variables per query. The output array of size q is required regardless of approach and is not counted as auxiliary space.

Why This Approach Is Not Efficient

The brute force approach recomputes the XOR from scratch for every query. This means if two queries overlap (e.g., [0,3] and [0,1]), we XOR the shared elements (indices 0 and 1) twice — wasting effort.

The inefficiency: With up to 3 × 10⁴ queries and arrays of length up to 3 × 10⁴, the worst case is O(n × q) ≈ 9 × 10⁸ operations. This exceeds typical time limits.

Key insight — Prefix XOR: Just like prefix sums let you compute the sum of any subarray in O(1) after O(n) preprocessing, a prefix XOR array lets you compute the XOR of any subarray in O(1).

Define prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] (with prefix[0] = 0). Then:

arr[left] ^ arr[left+1] ^ ... ^ arr[right] = prefix[right+1] ^ prefix[left]

Why this works: prefix[right+1] contains the XOR of elements 0 through right. prefix[left] contains the XOR of elements 0 through left-1. XOR-ing these two cancels the elements 0 through left-1 (since a ^ a = 0), leaving only elements left through right.

This reduces each query to a single O(1) lookup, giving O(n + q) total time.

Optimal Approach - Prefix XOR Array

Intuition

The prefix XOR technique is analogous to prefix sums — a fundamental technique for range queries. With prefix sums, if you want the sum of elements from index l to r, you compute prefixSum[r+1] - prefixSum[l]. The subtraction "removes" the elements before l.

With XOR, the same idea applies, but instead of subtraction, we use XOR itself as the "undo" operation. Since a ^ a = 0 (XOR is its own inverse), XOR-ing the prefix value at r+1 with the prefix value at l cancels out all elements before index l.

Building the prefix array:

  • prefix[0] = 0 (identity element for XOR)
  • prefix[1] = arr[0]
  • prefix[2] = arr[0] ^ arr[1]
  • prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]

Answering a query [l, r]:

  • answer = prefix[r+1] ^ prefix[l]
  • This cancels elements 0..l-1, leaving elements l..r

The preprocessing takes O(n), and each query takes O(1). For q queries, total time is O(n + q) — a massive improvement over O(n × q).

Step-by-Step Explanation

Let's trace arr = [1, 3, 4, 8], queries = [[0,1], [1,2], [0,3], [3,3]]:

Phase 1: Build Prefix XOR Array

  • prefix[0] = 0 (base case)
  • prefix[1] = prefix[0] ^ arr[0] = 0 ^ 1 = 1
  • prefix[2] = prefix[1] ^ arr[1] = 1 ^ 3 = 2
  • prefix[3] = prefix[2] ^ arr[2] = 2 ^ 4 = 6
  • prefix[4] = prefix[3] ^ arr[3] = 6 ^ 8 = 14
  • prefix = [0, 1, 2, 6, 14]

Phase 2: Answer Queries in O(1) each

  • Query [0,1]: prefix[1+1] ^ prefix[0] = prefix[2] ^ prefix[0] = 2 ^ 0 = 2 ✓
  • Query [1,2]: prefix[2+1] ^ prefix[1] = prefix[3] ^ prefix[1] = 6 ^ 1 = 7 ✓
  • Query [0,3]: prefix[3+1] ^ prefix[0] = prefix[4] ^ prefix[0] = 14 ^ 0 = 14 ✓
  • Query [3,3]: prefix[3+1] ^ prefix[3] = prefix[4] ^ prefix[3] = 14 ^ 6 = 8 ✓

Output: [2, 7, 14, 8]

Building the Prefix XOR Array for arr = [1, 3, 4, 8] — Watch how the prefix XOR array is built incrementally. Each new entry XORs the previous prefix with the current array element, accumulating the running XOR.

Answering Queries in O(1) Using Prefix XOR — Watch how each query is answered instantly by looking up just two values in the prefix array and XOR-ing them. No iteration over array elements needed.

Algorithm

Phase 1: Build Prefix XOR Array (O(n))

  1. Create array prefix of size n + 1
  2. Set prefix[0] = 0
  3. For i from 0 to n - 1:
    • prefix[i + 1] = prefix[i] ^ arr[i]

Phase 2: Answer Queries (O(q))
4. For each query [left, right]:

  • answer[i] = prefix[right + 1] ^ prefix[left]
  1. Return answer

Why the formula works:

  • prefix[right + 1] = arr[0] ^ arr[1] ^ ... ^ arr[right]
  • prefix[left] = arr[0] ^ arr[1] ^ ... ^ arr[left - 1]
  • XOR-ing them: elements 0 through left-1 appear in both and cancel out (a ^ a = 0)
  • What remains: arr[left] ^ arr[left+1] ^ ... ^ arr[right]

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        
        // Build prefix XOR array of size n + 1
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        // Answer each query in O(1)
        vector<int> answer;
        for (auto& query : queries) {
            int left = query[0];
            int right = query[1];
            answer.push_back(prefix[right + 1] ^ prefix[left]);
        }
        
        return answer;
    }
};
from typing import List

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        
        # Build prefix XOR array of size n + 1
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ arr[i]
        
        # Answer each query in O(1)
        answer = []
        for left, right in queries:
            answer.append(prefix[right + 1] ^ prefix[left])
        
        return answer
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        
        // Build prefix XOR array of size n + 1
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        // Answer each query in O(1)
        int[] answer = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int left = queries[q][0];
            int right = queries[q][1];
            answer[q] = prefix[right + 1] ^ prefix[left];
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n + q)

Building the prefix XOR array requires one pass through the array: O(n). Each of the q queries is answered in O(1) by looking up two prefix values and XOR-ing them. Total: O(n + q).

Compared to the brute force O(n × q), this is a massive improvement. For n = q = 3 × 10⁴, we go from up to 9 × 10⁸ operations down to 6 × 10⁴ — a 15,000× speedup.

Space Complexity: O(n)

The prefix XOR array has n + 1 elements. This is the only additional data structure used. The output array of size q is required by the problem and not counted as auxiliary space.

Why this is optimal: We must read every element of the array at least once (to handle queries that touch every position), so Ω(n) is a lower bound. We must also produce q answers, so Ω(q) is a lower bound. Our O(n + q) solution matches both lower bounds and is therefore asymptotically optimal.