XOR Queries of a Subarray

Problem

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.

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 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]

Solution

Method 1 - Using Prefix xor

Here are the steps:

1. Prefix XOR Array:
   • Create a prefix XOR array where prefix[i] stores the XOR of all elements from the beginning of the array up to (and including) the i-th element.
   • This helps in computing the XOR of any subarray in constant time.
2. Subarray XOR Calculation:
   • For each query [left_i, right_i], the XOR of the subarray can be quickly calculated using the prefix XOR array: $\text{XOR}(left_i, right_i) = \text{prefix}[right_i] \text{ XOR } \text{prefix}[left_i - 1]$
   • If left_i is 0, then it is just prefix[right_i], as there are no elements to exclude from the start.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/E6HX-n1KSPk" frameborder="0" allowfullscreen></iframe></div>

Code

Java

public class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        // Step 1: Compute the prefix XOR array
        int n = arr.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }

        // Step 2: Answer each query using the prefix XOR array
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            answer[i] = prefix[right + 1] ^ prefix[left];
        }

        return answer;
    }
}

Python

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        # Step 1: Compute the prefix XOR array
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ arr[i]

        # Step 2: Answer each query using the prefix XOR array
        answer = []
        for left, right in queries:
            answer.append(prefix[right + 1] ^ prefix[left])

        return answer

Complexity

• ⏰ Time complexity: O(n + q) where n is number of elements in arr, and q is number of queries
  • Creating the prefix XOR array involves a single pass through the arr array ⇨ O(n)
  • Each query is answered in constant time (O(1)) using the prefix XOR array ⇨ O(q)
• 🧺 Space complexity: O(n + q)
  • O(n) for the prefix XOR array.
  • O(q) for storing the results of the queries.

Dry Run

• Prefix XOR Array:
  • For arr = [1, 3, 4, 8], the prefix array will be computed as follows:
    • prefix[0] = 0
    • prefix[1] = 1 (since 0 ^ 1 = 1)
    • prefix[2] = 2 (since 1 ^ 3 = 2)
    • prefix[3] = 6 (since 2 ^ 4 = 6)
    • prefix[4] = 14 (since 6 ^ 8 = 14)
  • The final prefix array will be: [0, 1, 2, 6, 14].
• Using Prefix XOR for Queries:
  • For query [0, 1]:

- For query `[1, 2]`:

- For query `[0, 3]`:

- For query `[3, 3]`:

This code efficiently computes the XOR for each query using the prefix XOR array, allowing for rapid query responses.