XOR Queries of a Subarray
MedPrompt
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] = 8Example 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 * 1041 <= arr[i] <= 109queries[i].length == 20 <= lefti <= righti < arr.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. For each query, it iterates through the specified subarray and calculates the XOR sum of its elements.
Algorithm
1. Initialize an integer array `results` with the same size as `queries`.2. Loop through each query `q` from `i = 0` to `queries.length - 1`.3. Let `left = q[0]` and `right = q[1]`.4. Initialize a variable `xorSum = 0`.5. Loop from `j = left` to `right`.6. Update `xorSum` by XORing it with `arr[j]`: `xorSum = xorSum ^ arr[j]`.7. After the inner loop, set `results[i] = xorSum`.8. After processing all queries, return the `results` array.class Solution { public int[] xorQueries(int[] arr, int[][] queries) { int[] results = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int left = queries[i][0]; int right = queries[i][1]; int xorSum = 0; for (int j = left; j <= right; j++) { xorSum ^= arr[j]; } results[i] = xorSum; } return results; }}Walkthrough
The simplest way to solve this problem is to handle each query independently. We loop through the queries array. For each query [left, right], we initialize a variable, say currentXor, to 0. Then, we start another loop that iterates from the left index to the right index of the arr array. In each step of this inner loop, we XOR the current element arr[j] with currentXor. After the inner loop finishes, currentXor holds the XOR sum for the subarray arr[left...right]. We store this result in our answer array and move to the next query. This process is repeated for all queries.
Complexity
Time
O(N * Q), where N is the length of `arr` and Q is the number of queries. For each of the Q queries, we might iterate up to N elements in the worst case (when the query range is the entire array). This leads to a quadratic time complexity, which is too slow for the given constraints and will likely result in a Time Limit Exceeded (TLE) error.
Space
O(Q) to store the result array. If the output array is not considered part of the space complexity, then it is O(1) as we only use a few variables to calculate the XOR sum for each query.
Trade-offs
Pros
Very simple to understand and implement.
It's a direct translation of the problem's requirements.
Cons
Highly inefficient due to re-computation for overlapping subarray ranges.
Fails to pass within the time limits for larger inputs as specified in the constraints.
Solutions
Solution
class Solution {public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[] s = new int[n + 1]; for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] ^ arr[i - 1]; } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int l = queries[i][0], r = queries[i][1]; ans[i] = s[r + 1] ^ s[l]; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.