Leetcode 1310. XOR Queries of a Subarray

Problem Explanation:

The problem wants us to return XOR of elements for each pair of indices in the array. For example, given array [1, 3, 4, 8] and indices [0,1] i.e arr[0] and arr[1] the XOR(1, 3) gives us 2.

The solution overview:

To make it efficient, we use a xor prefix sum array that will calculate the xor from the first element to the current element for every element, which will help us to calculate the xor for any range in constant time. For any query pair Li, Ri, the XOR of any range can be calculated using: prefix[Ri+1] XOR prefix[Li], because the prefix array stores the xor from the start of the array to the current position.

Let's walk through an example to understand it better. Suppose following arrays are given: arr = [4,8,2,10] and queries = [[2,3],[1,3],[0,0],[0,3]].

1. First, we prepare prefix array, prefix[0] = 0 as there is no element at 0th index, prefix[1] = arr[0] which is 4, prefix[2] = arr[0] XOR arr[1] which is 4 XOR 8 = 4, prefix[3] = arr[0] XOR arr[1] XOR arr[2] which is 4 XOR 8 XOR 2 = 6 and prefix[4] = arr[0] XOR arr[1] XOR arr[2] XOR arr[3] which is 4 XOR 8 XOR 2 XOR 10 = 14.

2. Now prefix array looks like = [0, 4, 12, 14, 4].

3. For each query, we calculate xor = prefix[Li] XOR prefix[Ri+1]. For query [2,3] xor = prefix[2] XOR prefix[3+1] which is 12 XOR 4 = 8.

4. We keep pushing these results in our answer array.

Using this strategy, we can easily solve this problem with a time complexity of O(n), where n is the length of arr[].

1
2python
3class Solution:
4    def xorQueries(self, arr, queries):
5        prefix = [0]
6        for i in arr:
7            prefix.append(prefix[-1] ^ i)
8        return [prefix[i] ^ prefix[j+1] for i, j in queries]

1
2java
3class Solution {
4    public int[] xorQueries(int[] arr, int[][] queries) {
5        for (int i = 1; i < arr.length; ++i)
6            arr[i] ^= arr[i - 1];
7        int[] ans = new int[queries.length];
8        for (int i = 0; i < queries.length; ++i)
9            ans[i] = queries[i][0] > 0 
10            ? arr[queries[i][1]] ^ arr[queries[i][0] - 1] 
11            : arr[queries[i][1]];
12        return ans;
13    }
14}

1
2c++
3class Solution {
4public:
5    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
6        for (int i = 1; i < arr.size(); ++i)
7            arr[i] ^= arr[i - 1];
8        vector<int> ans;
9        for (auto& q: queries)
10            ans.push_back(q[0] > 0 ? arr[q[1]] ^ arr[q[0] - 1] : arr[q[1]]);
11        return ans;
12    }
13};

1
2csharp
3public class Solution {
4    public int[] XorQueries(int[] arr, int[][] queries) {
5        for (int i = 1; i < arr.Length; i++)
6            arr[i] ^= arr[i - 1];
7        int[] result = new int[queries.Length];
8        for (int i = 0; i < queries.Length; i++)
9            result[i] = queries[i][0] > 0 
10            ? arr[queries[i][1]] ^ arr[queries[i][0] - 1]
11            : arr[queries[i][1]];
12        return result;
13    }
14}

1
2javascript
3var xorQueries = function(arr, queries) {
4    for (let i = 1; i < arr.length; i++)
5        arr[i] ^= arr[i - 1];
6    let res = [];
7    for (let i = 0; i < queries.length; i++) {
8        if (queries[i][0] === 0) 
9            res.push(arr[queries[i][1]]);
10        else 
11            res.push(arr[queries[i][1]] ^ arr[queries[i][0] - 1]);
12    }
13    return res;
14};

Note: The caret (^) operator represents the bitwise XOR operation.## Conclusion

In this article, we have discussed an effective approach to solve the problem of Return XOR of elements for each pair of indices in the array. By first calculating a prefix sum array via XOR and then using those sums in conjunction with the queries, we're able to solve this problem with a time complexity of O(n). The prefix sum array allows us to calculate the XOR for any range in O(1) time. The XOR operation is represented by the caret (^) operator in many programming languages.

We've also provided solutions in multiple Programming languages, Python, JavaScript, Java, C++ and C#. This makes it easier to understand how to implement this approach in your programming language of choice.

The use of bitwise operations as in this problem is a common pattern in many programming challenges. They often allow for very efficient solutions, as they work directly with the information representation in memory. These bitwise operations, including XOR, are a valuable tool in every programmer's toolkit. As with many aspects of programming, the key to getting comfortable with them is practice.

Next time you encounter a problem involving ranges in an array, consider if a prefix sum array might be helpful. And if you see an operation that just seems like it should be simpler, see if bitwise operations are the key. They just might be the efficient solution you're looking for.