1442. Count Triplets That Can Form Two Arrays of Equal XOR
Difficulty: Medium
Topics: Array
, Hash Table
, Math
, Bit Manipulation
, Prefix Sum
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 <= 300
1 <= arr[i] <= 108
Hint:
- We are searching for sub-array of length ≥ 2 and we need to split it to 2 non-empty arrays so that the xor of the first array is equal to the xor of the second array. This is equivalent to searching for sub-array with xor = 0.
- Keep the prefix xor of arr in another array, check the xor of all sub-arrays in O(n^2), if the xor of sub-array of length x is 0 add x-1 to the answer.
Solution:
The problem asks us to count the number of triplets (i, j, k)
where the XOR of elements between i
and j-1
(inclusive) equals the XOR of elements between j
and k
(inclusive) in the given array arr
.
The XOR operation is a bitwise operation where each bit is evaluated independently, and the result is 1
if the corresponding bits in the operands are different, and 0
if they are the same.
Key Points:
- We are given an array of integers
arr
. - We need to find triplets
(i, j, k)
such that the XOR of elements from indexi
toj-1
equals the XOR of elements from indexj
tok
. - The XOR operation has some important properties, such as
x ^ x = 0
andx ^ 0 = x
, which can help optimize the solution.
Approach:
To solve this problem efficiently, we can utilize the concept of prefix XORs, which allows us to calculate the XOR of any subarray in constant time. The main idea is to compute the cumulative XOR for each element and use it to determine if the conditions of the triplets are met.
Plan:
-
Prefix XORs: Compute an array
xors
wherexors[i]
holds the XOR of all elements fromarr[0]
toarr[i-1]
. This helps calculate the XOR of any subarray efficiently. -
Loop through
j
: Iterate through possible values forj
. For eachj
, try all possible values fori
andk
. -
Condition check: For each combination of
i
,j
, andk
, check if the XOR fromi
toj-1
is equal to the XOR fromj
tok
. - Count valid triplets: If the condition is met, increment the count.
Let's implement this solution in PHP: 1442. Count Triplets That Can Form Two Arrays of Equal XOR
<?php
/**
* @param Integer[] $arr
* @return Integer
*/
function countTriplets($arr) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$arr1 = [2,3,1,6,7];
$arr2 = [1,1,1,1,1];
echo countTriplets($arr1) . "\n"; // Output: 4
echo countTriplets($arr2) . "\n"; // Output: 10
?>
Explanation:
prefix = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
- We use an auxiliary array
xors[]
to store the cumulative XOR values, which allows us to compute the XOR of any subarray in constant time. - For each pair of indices
i
andj
, we can check if the XOR between them is the same as the XOR betweenj
andk
, thus finding the valid triplets.
Example Walkthrough:
Example 1:
Input: [2, 3, 1, 6, 7]
- We first calculate the prefix XORs for the array:
xors = [0, 2, 1, 0, 6, 1]
Now, we loop through possible values for j
:
- For
j = 1
, check all possible pairs(i, k)
:- Triplet
(0,1,2)
:2 == 2
(valid) - Triplet
(0,2,2)
:2 == 2
(valid)
- Triplet
- For
j = 2
, check:- Triplet
(2,3,4)
:0 == 0
(valid) - Triplet
(2,4,4)
:0 == 0
(valid)
- Triplet
Thus, the output is 4
.
Example 2:
Input: [1, 1, 1, 1, 1]
- Calculate prefix XORs:
xors = [0, 1, 0, 1, 0, 1]
Now, loop through possible values for j
:
- For
j = 1
, we check all combinations and find valid triplets. - Continue checking for each subsequent value of
j
until the final answer is reached.
Output: 10
Time Complexity:
-
Time Complexity: The solution iterates through the possible values of
i
,j
, andk
. For eachj
, there is anO(n)
loop fori
and anotherO(n)
loop fork
, resulting in a time complexity of O(n^3). -
Space Complexity: The space complexity is O(n) due to the storage required for the
xors
array.
Output for Example:
- For
arr = [2, 3, 1, 6, 7]
, the output is4
. - For
arr = [1, 1, 1, 1, 1]
, the output is10
.
This solution efficiently calculates the number of valid triplets using prefix XORs. While the time complexity can be improved further, the approach provides a straightforward way to solve the problem by utilizing properties of the XOR operation.
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:
Top comments (0)