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

 

1st approach

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int size = queries.size();
        vector<int> res(size);
        
        for(int i=0; i<size; i++){
            int left = queries[i][0];		//left is the leftmost index of "arr"
            int right = queries[i][1];
            int start = arr[left];		//starting number of series of XOR operations

            if(left==right){			//when left==right, the range is 0.
                res[i]=arr[left];

            }else{
                while(left<right){
                    left++;
                    start=start^arr[left];	//bitwise XOR until left<right
                }
                res[i]=start;
            }           
        }
        return res;
    }
};

 

faster runtime approach

 

Intuition
we can use a prefix XOR array where each element at index i represents the XOR of all elements from the start of the array to index i. This allows us to compute the XOR for any subarray in constant time

Approach
Compute Prefix XOR Array:
Build a prefix XOR array where prefix[i] holds the XOR of all elements from the start of the array up to index i. This can be done in a single pass through the array.

Answer Queries Using Prefix XOR Array:
For each query (left, right), if left is 0, the result is simply prefix[right].
If left is greater than 0, the result can be obtained by prefix[right] ^ prefix[left - 1]. This works because XORing with prefix[left - 1] effectively removes the elements before left, leaving the XOR of the subarray from left to right.

Complexity
Time complexity:
the total time complexity is O(n+q), where q is the number of queries & n is the size of arr.
Space complexity:
the space complexity is O(n+q). n is the space used to store ans & q is the space for prefix.

 

Code

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> prefix(n);
        vector<int> ans(queries.size());

        // Fill the prefix XOR array
        prefix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] ^ arr[i];
        }

        // Process each query
        for (int i = 0; i < queries.size(); i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            if (left == 0) {
                ans[i] = prefix[right];
            } else {
                ans[i] = prefix[right] ^ prefix[left - 1];
            }
        }

        return ans;
    }
};