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]

Constraints:

• 1 <= arr.length, queries.length <= 3 * 104
• 1 <= arr[i] <= 109
• queries[i].length == 2
• 0 <= lefti <= righti < arr.length

Approach 01

class Solution {
public:
    vector<int> xorQueries(vector<int>& inputArray, vector<vector<int>>& queries) {
        vector<int> result; // To store the result of each query
        vector<int> prefixXor(inputArray.size() + 1); // To store prefix XOR values

        // Calculate prefix XOR for the input array
        for (int i = 0; i < inputArray.size(); ++i)
            prefixXor[i + 1] = prefixXor[i] ^ inputArray[i];

        // Process each query
        for (const vector<int>& query : queries) {
            const int startIndex = query[0];
            const int endIndex = query[1];
            // XOR from startIndex to endIndex can be found using prefix XOR values
            result.push_back(prefixXor[startIndex] ^ prefixXor[endIndex + 1]);
        }

        return result;
    }
};

class Solution:
    def xorQueries(self, inputArray, queries):
        # To store prefix XOR values
        prefixXor = [0] * (len(inputArray) + 1)
        result = []  # To store the result of each query

        # Calculate prefix XOR for the input array
        for i in range(len(inputArray)):
            prefixXor[i + 1] = prefixXor[i] ^ inputArray[i]

        # Process each query
        for query in queries:
            startIndex = query[0]
            endIndex = query[1]
            # XOR from startIndex to endIndex can be found using prefix XOR values
            result.append(prefixXor[startIndex] ^ prefixXor[endIndex + 1])

        return result

Time Complexity

• Calculating Prefix XOR:

  We compute the prefix XOR values for the input array. This requires a single pass over the array, resulting in a time complexity of \(O(n)\), where n is the size of the input array.

• Processing Queries:

  For each query, we compute the XOR of a range using the prefix XOR values. Each query operation is performed in \(O(1)\) time. Let m be the number of queries; the total time complexity for processing all queries is \(O(m)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n + m)\), where n is the size of the input array and m is the number of queries.

Space Complexity

• Space for Prefix XOR Array:

  The prefix XOR array requires \(O(n)\) space, where n is the size of the input array.

• Space for Result Vector:

  The result vector stores the XOR values for each query, requiring \(O(m)\) space, where m is the number of queries.

• Overall Space Complexity:

  The overall space complexity is \(O(n + m)\), which accounts for the space needed for the prefix XOR array and the result vector.