Dare2Solve
To find the number of triplets (i, j, k)
where a == b
given the conditions, we can use the prefix XOR technique. The key observation is that if the XOR from i
to k
is zero (pref[i] == pref[k+1]
), it implies there exists at least one j
such that the XOR from i
to j-1
is equal to the XOR from j
to k
.
Prefix XOR Array:
pref
where pref[i]
is the XOR of all elements from the start of the array up to the i-1
index.pref[0]
to 0.pref[i]
for each i
from 1 to n
as pref[i] = pref[i - 1] ^ arr[i - 1]
.Find Triplets:
i
and k
.(i, k)
, check if pref[i] == pref[k + 1]
.k - i
, as there are k - i
valid values for j
between i
and k
.Return the Result:
(i, k)
take (O(n^2)) time.pref
requires (O(n)) space.int countTriplets(int* arr, int n) {
int pref[n + 1];
pref[0] = 0;
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (pref[i] == pref[k + 1]) {
res += k - i;
}
}
}
return res;
}
class Solution {
public:
int countTriplets(vector<int>& arr) {
int n = arr.size();
vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; ++i) {
for (int k = i + 1; k < n; ++k) {
if (pref[i] == pref[k + 1]) {
res += k - i;
}
}
}
return res;
}
};
class Solution:
def countTriplets(self, arr):
n = len(arr)
pref = [0] * (n + 1)
for i in range(1, n + 1):
pref[i] = pref[i - 1] ^ arr[i - 1]
res = 0
for i in range(n):
for k in range(i + 1, n):
if pref[i] == pref[k + 1]:
res += k - i
return res
class Solution {
public int countTriplets(int[] arr) {
int n = arr.length;
int[] pref = new int[n + 1];
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (pref[i] == pref[k + 1]) {
res += k - i;
}
}
}
return res;
}
}
/**
* @param {number[]} arr
* @return {number}
*/
var countTriplets = function (arr) {
var n = arr.length;
var pref = new Uint32Array(n + 1);
for (var i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ arr[i - 1];
var res = 0;
for (var i = 0; i < n; i++) {
for (var k = i + 1; k < n; k++) {
if (pref[i] === pref[k + 1]) res += k - i;
}
}
return res;
};
function countTriplets(arr: number[]): number {
var n = arr.length;
var pref = new Uint32Array(n + 1);
for (var i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ arr[i - 1];
var res = 0;
for (var i = 0; i < n; i++) {
for (var k = i + 1; k < n; k++) {
if (pref[i] === pref[k + 1]) res += k - i;
}
}
return res;
}
func countTriplets(arr []int) int {
n := len(arr)
pref := make([]int, n+1)
for i := 1; i <= n; i++ {
pref[i] = pref[i-1] ^ arr[i-1]
}
res := 0
for i := 0; i < n; i++ {
for k := i + 1; k < n; k++ {
if pref[i] == pref[k+1] {
res += k - i
}
}
}
return res
}
public class Solution {
public int CountTriplets(int[] arr) {
int n = arr.Length;
int[] pref = new int[n + 1];
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (pref[i] == pref[k + 1]) {
res += k - i;
}
}
}
return res;
}
}