# XOR Queries of a Subarray **Difficulty:** MEDIUM [External](https://leetcode.com/problems/xor-queries-of-a-subarray) Canonical: https://scaleengineer.com/dsa/problems/xor-queries-of-a-subarray **Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array **Companies:** [Airtel](https://scaleengineer.com/companies/airtel) --- ## Problem 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` # Approaches ## Brute Force Iteration 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. **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. **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. ### Explanation 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. ### Algorithm ```markdown 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. ``` ```java 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; } } ``` ## Prefix XOR Array 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. **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). **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`. ### Explanation 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. ### Algorithm ```markdown 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. ``` ```java 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; } } ``` # Solutions ### Java ```java 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; } } ``` ### JavaScript ```javascript /** * @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; }; ``` ### CPP ```cpp class Solution { public: vector xorQueries(vector &arr, vector> &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 ans; for (auto &q : queries) { int l = q[0], r = q[1]; ans.push_back(s[r + 1] ^ s[l]); } return ans; } }; ``` ### Python ```python 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] ```