1442. Count Triplets That Can Form Two Arrays of Equal XOR
Description
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
Solutions
Solution 1: Enumeration
According to the problem description, to find triplets $(i, j, k)$ that satisfy $a = b$, which means $s = a \oplus b = 0$, we only need to enumerate the left endpoint $i$, and then calculate the prefix XOR sum $s$ of the interval $[i, k]$ with $k$ as the right endpoint. If $s = 0$, then for any $j \in [i + 1, k]$, the condition $a = b$ is satisfied, meaning $(i, j, k)$ is a valid triplet. There are $k - i$ such triplets, which we can add to our answer.
After the enumeration is complete, we return the answer.
The time complexity is $O(n^2)$, where $n$ is the length of the array $\textit{arr}$. The space complexity is $O(1)$.
Python3
class Solution:
def countTriplets(self, arr: List[int]) -> int:
ans, n = 0, len(arr)
for i, x in enumerate(arr):
s = x
for k in range(i + 1, n):
s ^= arr[k]
if s == 0:
ans += k - i
return ans
Java
class Solution {
public int countTriplets(int[] arr) {
int ans = 0, n = arr.length;
for (int i = 0; i < n; ++i) {
int s = arr[i];
for (int k = i + 1; k < n; ++k) {
s ^= arr[k];
if (s == 0) {
ans += k - i;
}
}
}
return ans;
}
}
C++
class Solution {
public:
int countTriplets(vector<int>& arr) {
int ans = 0, n = arr.size();
for (int i = 0; i < n; ++i) {
int s = arr[i];
for (int k = i + 1; k < n; ++k) {
s ^= arr[k];
if (s == 0) {
ans += k - i;
}
}
}
return ans;
}
};
Go
func countTriplets(arr []int) (ans int) {
for i, x := range arr {
s := x
for k := i + 1; k < len(arr); k++ {
s ^= arr[k]
if s == 0 {
ans += k - i
}
}
}
return
}
TypeScript
function countTriplets(arr: number[]): number {
const n = arr.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
let s = arr[i];
for (let k = i + 1; k < n; ++k) {
s ^= arr[k];
if (s === 0) {
ans += k - i;
}
}
}
return ans;
}
Rust
impl Solution {
pub fn count_triplets(arr: Vec<i32>) -> i32 {
let mut ans = 0;
let n = arr.len();
for i in 0..n {
let mut s = arr[i];
for k in (i + 1)..n {
s ^= arr[k];
if s == 0 {
ans += (k - i) as i32;
}
}
}
ans
}
}