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 * 1041 <= arr[i] <= 109queries[i].length == 20 <= lefti <= righti < arr.lengthThis approach involves directly computing the XOR for each range specified in the queries. For each query, iterate over the specified subarray range and compute the XOR.
This C implementation uses a nested loop for each query. The outer loop iterates through each query, and the inner loop computes the XOR from the left index to the right index of each query, storing the result in the output array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries.
Space Complexity: O(q) for storing the query results.
To optimize the XOR computation, we can use a prefix XOR array. Compute the XOR of all elements up to each position in the array. Then to find the XOR for a range simply subtract the prefix value before the start of the range from the prefix at the end of the range.
This C implementation computes the prefix XOR array, which is then used to quickly compute the XOR for any subrange as the difference between the prefix XOR at right + 1 and left indices.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + q), where n is the number of elements and q is the number of queries.
Space Complexity: O(n) for the prefix XOR array.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * q), where n is the number of elements in the largest range and q is the number of queries. |
| Optimized Prefix XOR Approach | Time Complexity: O(n + q), where n is the number of elements and q is the number of queries. |
XOR Queries of a Subarray | Simple Explanation | Leetcode 1310 | codestorywithMIK • codestorywithMIK • 6,738 views views
Watch 9 more video solutions →Practice XOR Queries of a Subarray with our built-in code editor and test cases.
Practice on FleetCode