Closed mah-shamim closed 4 days ago
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:
left
and right
:
left > 0
, we can compute the XOR from left
to right
as prefix[right] ^ prefix[left - 1]
.left == 0
, then the result is simply prefix[right]
.This allows us to answer each query in constant time after constructing the prefix XOR array.
[left_i, right_i]
.Let's implement this solution in PHP: 1310. XOR Queries of a Subarray
<?php
function xorQueries($arr, $queries) {
$n = count($arr);
$prefix = array_fill(0, $n, 0);
$prefix[0] = $arr[0];
// Build the prefix XOR array
for ($i = 1; $i < $n; $i++) {
$prefix[$i] = $prefix[$i - 1] ^ $arr[$i];
}
$result = [];
// Process each query
foreach ($queries as $query) {
list($left, $right) = $query;
if ($left == 0) {
$result[] = $prefix[$right];
} else {
$result[] = $prefix[$right] ^ $prefix[$left - 1];
}
}
return $result;
}
// 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:
prefix
is built such that prefix[i]
contains the XOR of all elements from arr[0]
to arr[i]
.arr = [1, 3, 4, 8]
, the prefix
array will be [1, 1^3, 1^3^4, 1^3^4^8]
or [1, 2, 6, 14]
.Answering Queries:
[left, right]
, we compute the XOR of the subarray arr[left]
to arr[right]
using:
prefix[right] ^ prefix[left - 1]
(if left > 0
)prefix[right]
(if left == 0
)n
is the length of the arr
.q
is the number of queries.This approach ensures we can handle up to 30,000 queries on an array of size up to 30,000 efficiently.
Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/534
queries[i] = [lefti, righti]
. For each query `i` compute the XOR of elements fromlefti
torighti
(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
**Hint:** 1. What is the result of x ^ y ^ x ? 2. Compute the prefix sum for XOR. 3. Process the queries with the prefix sum values.