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.
This is an optimized approach that uses a pre-computation technique. We create a prefix XOR array to store the XOR sum of elements from the start of the array up to each index. This allows us to calculate the XOR sum of any subarray in constant time.
Algorithm
1. Create a prefix XOR array, `prefixXor`, of size `arr.length + 1`.2. Initialize `prefixXor[0] = 0`.3. Iterate from `i = 0` to `arr.length - 1`: - Calculate `prefixXor[i + 1] = prefixXor[i] ^ arr[i]`.4. Initialize an integer array `results` of size `queries.length`.5. Loop through each query `q` from `i = 0` to `queries.length - 1`.6. Let `left = q[0]` and `right = q[1]`.7. The XOR sum for the range `[left, right]` is `prefixXor[right + 1] ^ prefixXor[left]`.8. Store this result in `results[i]`.9. After processing all queries, return the `results` array.class Solution { public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[] prefixXor = new int[n + 1]; // prefixXor[0] is 0 for (int i = 0; i < n; i++) { prefixXor[i + 1] = prefixXor[i] ^ arr[i]; } int[] results = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int left = queries[i][0]; int right = queries[i][1]; // XOR sum of arr[left...right] is // (XOR sum of arr[0...right]) ^ (XOR sum of arr[0...left-1]) // which is prefixXor[right + 1] ^ prefixXor[left] results[i] = prefixXor[right + 1] ^ prefixXor[left]; } return results; }}Walkthrough
The core idea is based on the properties of the XOR operation, specifically a ^ a = 0 and (a ^ b ^ c) ^ (a ^ b) = c. We can pre-calculate the XOR sum from the beginning of the array up to every index. Let's define prefixXor[i] as the XOR sum of arr[0] ^ arr[1] ^ ... ^ arr[i-1]. We can build this array in a single pass. prefixXor[0] is initialized to 0, and for i > 0, prefixXor[i] = prefixXor[i-1] ^ arr[i-1].
Once we have this prefixXor array, the XOR sum of a subarray arr[left...right] can be found efficiently. The XOR sum from left to right is (arr[0] ^ ... ^ arr[right]) ^ (arr[0] ^ ... ^ arr[left-1]). In terms of our prefix array, this is prefixXor[right + 1] ^ prefixXor[left]. This calculation takes constant time for each query. Therefore, after an initial O(N) pre-computation step, each of the Q queries can be answered in O(1) time.
Complexity
Time
O(N + Q), where N is the length of `arr` and Q is the number of queries. It takes O(N) to build the prefix XOR array and O(Q) to process all the queries, as each query takes O(1) time. This is a significant improvement and is efficient enough to pass the given constraints.
Space
O(N + Q). We need O(N) extra space for the `prefixXor` array and O(Q) space for the result array. If the output array is not considered, the space complexity is O(N).
Trade-offs
Pros
Extremely fast query time (O(1) per query).
Efficient overall time complexity that handles large inputs well.
It's a classic and reusable pattern for range-based query problems.
Cons
Requires additional space proportional to the size of the input array
arr.
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; }}/** * @param {number[]} arr * @param {number[][]} queries * @return {number[]} */ var xorQueries = function (arr, queries) { const n = arr.length; const s = new Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] ^ arr[i]; } const ans = []; for (const [l, r] of queries) { ans.push(s[r + 1] ^ s[l]); } return ans; };class Solution {public: vector<int> xorQueries(vector<int> &arr, vector<vector<int>> &queries) { int n = arr.size(); int s[n + 1]; memset(s, 0, sizeof(s)); for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] ^ arr[i - 1]; } vector<int> ans; for (auto &q : queries) { int l = q[0], r = q[1]; ans.push_back(s[r + 1] ^ s[l]); } return ans; }};class Solution: def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]: s = list(accumulate(arr, xor, initial=0)) return [s[r + 1] ^ s[l] for l, r in queries]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.