Leetcode-1310. 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]

The task is to compute the XOR of elements in a given array `arr` for specific ranges specified in the `queries` array. Each query in `queries` defines a subarray in `arr` using a starting index (`lefti`) and an ending index (`righti`), and we need to compute the XOR of all elements within this range for each query.

- A variable `sum` is initialized to 0 for computing the XOR value for each query. A vector `ans` is created to store the results of all queries.

- The outer loop iterates over the array `qrr`, which contains all the queries. For each query, the start (`qrr[j][0]`) and end (`qrr[j][1]`) indices of the range are used to extract the relevant portion of `arr`.

- For the current query, the inner loop iterates through the elements of `arr` from the start to the end indices specified in the query. During this iteration:

- The XOR operation is applied to each element in the range using `sum ^= arr[i]`.

- This operation cumulatively calculates the XOR of all elements in the specified range.

- After completing the XOR computation for a query, the value of `sum` is added to the result vector `ans` using `ans.push_back(sum)`.

- After processing all queries, the function returns the `ans` vector containing the XOR values for each query.

Example Walkthrough:

- Input: `arr = [1,3,4,8]`, `queries = [[0,1],[1,2],[0,3],[3,3]]`

- Query [0,1]: Range: `arr[0] XOR arr[1] = 1 XOR 3 = 2`. Result: `2`

- Query [1,2]: Range: `arr[1] XOR arr[2] = 3 XOR 4 = 7`. Result: `7`

- Query [0,3]: Range: `arr[0] XOR arr[1] XOR arr[2] XOR arr[3] = 1 XOR 3 XOR 4 XOR 8 = 14`. Result: `14`

- Query [3,3]: Range: `arr[3] = 8`. Result: `8`

- Final Output: `[2, 7, 14, 8]`

- Input: `arr = [4,8,2,10]`, `queries = [[2,3],[1,3],[0,0],[0,3]]`

- Query [2,3]: XOR of `arr[2]` and `arr[3]` = `2 XOR 10 = 8`

- Query [1,3]: XOR of `arr[1] XOR arr[2] XOR arr[3] = 8 XOR 2 XOR 10 = 0`

- Query [0,0]: Single element `arr[0] = 4`

- Query [0,3]: XOR of the entire array = `4 XOR 8 XOR 2 XOR 10 = 4`

- Final Output: `[8, 0, 4, 4]`

The solution uses two nested loops: the outer loop iterates over the queries, and the inner loop iterates over the range defined by each query. This results in a time complexity of O(n * m), where `n` is the number of queries and `m` is the average range length. The solution uses additional space for the result vector `ans`, making it O(n).

CODE:

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& qrr) {
        int sum=0;
        vector<int>ans;
        int n=qrr.size();
        int i,j;
        for(j=0;j<n;j++){
            sum=0;
        for(i=qrr[j][0];i<=qrr[j][1];i++){
           sum^=arr[i];
         }
        ans.push_back(sum);
       }
    return ans;
    }
};