{x}
blog image

XOR Queries of a Subarray

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith 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 * 104
  • 1 <= arr[i] <= 109
  • queries[i].length == 2
  • 0 <= lefti <= righti < arr.length

Solution Explanation: XOR Queries of a Subarray

This problem asks to compute the XOR of elements within given subarrays of an input array. A naive approach would involve iterating through each subarray for every query, leading to a time complexity of O(n*m), where 'n' is the length of the input array and 'm' is the number of queries. However, a more efficient solution leverages the properties of the XOR operation and prefix sums.

Approach: Prefix XOR Array

The core idea is to pre-compute a prefix XOR array. This array, denoted as s, stores the XOR sum of all elements up to a given index. Specifically, s[i] contains the XOR of arr[0], arr[1], ..., arr[i-1].

Once the prefix XOR array is computed, the XOR sum of any subarray arr[l...r] can be efficiently calculated using the following property:

arr[l] XOR arr[l+1] XOR ... XOR arr[r] = s[r+1] XOR s[l]

This is because the XOR operation cancels out the common elements in the prefix sums. For example:

s[r+1] = arr[0] XOR arr[1] XOR ... XOR arr[r]

s[l] = arr[0] XOR arr[1] XOR ... XOR arr[l-1]

Therefore, s[r+1] XOR s[l] effectively computes the XOR of elements from index l to r.

Time and Space Complexity

  • Time Complexity: O(n + m). The prefix XOR array is computed in O(n) time. Calculating the XOR sum for each query takes O(1) time, resulting in O(m) time for all queries.

  • Space Complexity: O(n). This is due to the space required to store the prefix XOR array s.

Code Implementation (Python)

from itertools import accumulate
from operator import xor
 
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        s = list(accumulate(arr, xor, initial=0))  #Efficiently calculate prefix XOR sums
        return [s[r + 1] ^ s[l] for l, r in queries] #Compute XOR for each query

Explanation:

  1. accumulate(arr, xor, initial=0): This utilizes the accumulate function from the itertools module to efficiently compute the prefix XOR sums. xor is the function applied cumulatively, and initial=0 sets the initial value of the accumulator.

  2. List Comprehension: The list comprehension iterates through the queries list, and for each query [l, r], it calculates s[r+1] ^ s[l] and adds the result to the output list.

Code Implementation (Other Languages)

The same approach can be implemented in other languages like Java, C++, JavaScript, and Go. The core logic remains identical; only the syntax changes. The provided solution includes examples in these languages.

The key improvement in this approach lies in pre-computing the prefix XOR sums, allowing for constant-time calculation of XOR sums for each query. This drastically reduces the overall time complexity compared to a naive approach.