1310. XOR Queries of a Subarray

1310. XOR Queries of a Subarray

Difficulty: Medium

Topics: Array, Bit Manipulation, Prefix Sum

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 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 * 104


• 1 <= arr[i] <= 109


• queries[i].length == 2


• 0 <= lefti <= righti < arr.length

Hint:

1. What is the result of x ^ y ^ x ?


2. Compute the prefix sum for XOR.


3. Process the queries with the prefix sum values.

Solution:

We can make use of the prefix XOR technique. Here's how it works:

Approach:

1. Prefix XOR Array: We compute a prefix XOR array where prefix[i] represents the XOR of all elements from the start of the array up to index i. This allows us to compute the XOR of any subarray in constant time.



2. 
   

   XOR of a subarray:

   
   
   
   
   
   • To compute the XOR of elements between indices left and right:
     
     
     
     
     • If left > 0, we can compute the XOR from left to right as prefix[right] ^ prefix[left - 1].
     
     
     • If left == 0, then the result is simply prefix[right].
     
     
     
     
   
   
   
   

This allows us to answer each query in constant time after constructing the prefix XOR array.

Plan:

1. Build the prefix XOR array.


2. For each query, use the prefix XOR array to compute the XOR for the range [left_i, right_i].

Let's implement this solution in PHP: a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me: