1310. XOR Queries of a Subarray
Difficulty: Medium
Topics: Array, Bit Manipulation, Prefix Sum
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:
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:
Constraints:
Hint:
Solution:
We can make use of the prefix XOR technique. Here's how it works:
Prefix XOR Array: We compute a prefix XOR array where prefix[i] represents the XOR of all elements from the start of the array up to index i. This allows us to compute the XOR of any subarray in constant time.
XOR of a subarray:
This allows us to answer each query in constant time after constructing the prefix XOR array.
Let's implement this solution in PHP: 1310. XOR Queries of a Subarray
<?php /** * @param Integer[] $arr * @param Integer[][] $queries * @return Integer[] */ function xorQueries($arr, $queries) { ... ... ... /** * go to ./solution.php */ } // Example 1 $arr1 = [1, 3, 4, 8]; $queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]]; print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8] // Example 2 $arr2 = [4, 8, 2, 10]; $queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]]; print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4] ?>
Prefix XOR Construction:
Answering Queries:
This approach ensures we can handle up to 30,000 queries on an array of size up to 30,000 efficiently.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
以上是XOR Queries of a Subarray的详细内容。更多信息请关注PHP中文网其他相关文章!