XOR Queries of a Subarray

Leetcode Problem:

• XOR Queries of a Subarray

Summary

• Given an array of positive integers and queries where each query is a range, compute the XOR of elements in the range for each query.

Approach

• The approach is to first compute the XOR of all elements in the array and then for each query, compute the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range.

Complexity

• O(n + q) where n is the size of the array and q is the number of queries

Explain

• The solution first computes the XOR of all elements in the array by iterating over the array and XORing each element with the previous one
• Then for each query, it computes the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range
• This is done by accessing the element at the end of the range and the element at the position before the end of the range, and XORing them
• The result is then added to the answer vector.

Solution Code:

class Solution {
public:
    vector xorQueries(vector& arr, vector>& queries) {
        vector ans;
        for(int i = 1 ; i < arr.size(); i++){
            arr[i] = arr[i] ^ arr[i-1];
        }
        for(int i = 0 ; i < queries.size(); i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            ans.push_back(arr[b] ^ (a-1 < 0 ? 0 : arr[a-1]));
        }
        return ans;
    }
};