1442. Count Triplets That Can Form Two Arrays of Equal XOR
Medium
Given an array of integers arr.
We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).
Let's define a and b as follows:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (i, j and k) Where a == b.
Example 1:
- Input: arr = [2,3,1,6,7]
- Output: 4
- Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)
Example 2:
- Input: arr = [1,1,1,1,1]
- Output: 10
Constraints:
1 <= arr.length <= 3001 <= arr[i] <= 108
Solution:
class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function countTriplets($arr) {
$ans = 0;
$xors = [0];
$prefix = 0;
foreach ($arr as $key => $a) {
$prefix ^= $a;
$xors[] = $prefix;
}
for ($j = 1; $j < count($arr); $j++) {
for ($i = 0; $i < $j; $i++) {
$xors_i = $xors[$j] ^ $xors[$i];
for ($k = $j; $k < count($arr); $k++) {
$xors_k = $xors[$k + 1] ^ $xors[$j];
if ($xors_i == $xors_k) {
$ans += 1;
}
}
}
}
return $ans;
}
}
Contact Links
Top comments (0)