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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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:

1
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:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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]: $$ \text{XOR}(0, 1) = \text{prefix}[2] \text{ XOR } \text{prefix}[0] = 2 \text{ XOR } 0 = 2 $$
    • For query [1, 2]: $$ \text{XOR}(1, 2) = \text{prefix}[3] \text{ XOR } \text{prefix}[1] = 6 \text{ XOR } 1 = 7 $$
    • For query [0, 3]: $$ \text{XOR}(0, 3) = \text{prefix}[4] \text{ XOR } \text{prefix}[0] = 14 \text{ XOR } 0 = 14 $$
    • For query [3, 3]: $$ \text{XOR}(3, 3) = \text{prefix}[4] \text{ XOR } \text{prefix}[3] = 14 \text{ XOR } 6 = 8 $$

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