Leetcode Daily Question 13/09/2024 - 1310. XOR Queries of a Subarray

Problem Description:

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.

from typing import List
class Solution:
  def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
    prefix_xor = [0] 
    px = 0
    for num in arr:
      px ^= num
      prefix_xor.append(px)
    
    result = []
    for start, end in queries:
      result.append(prefix_xor[end + 1] ^ prefix_xor[start])
    
    return result

Explanation:

To do this efficiently, we first note that xor is a reversible operator, meaning that if we do x ^ b we can do x ^ b ^ x to get back b.

We also utilise prefix xor sum to eliminate the need to iterate through the array arr everytime we make a query.

For example if we have the query
[2,3].
prefix_xor[1] = arr[0] ^ arr[1]
prefix_xor[3] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3],
so we can do prefix_xor[3] ^ prefix_xor[1] to get what we want.

Additionally, We can initiate prefix_xor with [0].

This makes it easy to deal with the case where the start of the query is at 0.

This also makes the handling of queries uniform, as we just need to shift our formula one to the right.

def xorQueries(arr, queries):
  prefix_xor = [0] 
  px = 0
  for num in arr:
    px ^= num
    prefix_xor.append(px)
  
  result = []
  for start, end in queries:
    result.append(prefix_xor[end + 1] ^ prefix_xor[start])
  
  return result

The time complexity of this is O(m + n), where n is the length of arr and m is the number of queries.

The space complexity of this is O(n), as we need to store the prefix sum. The storing of the result is O(m) but m <= n so O(n) dominates.

The full solution can be found near the top of the page.