Count Triplets That Can Form Two Arrays of Equal XOR
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
Example 3:
Input: arr = [2,3]
Output: 0
Example 4:
Input: arr = [1,3,5,7,9]
Output: 3
Example 5:
Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8
Constraints:
1 <= arr.length <= 300
1 <= arr[i] <= 10^8
Solution:
you have an array : a[0], a[1].... a[n - 1]
First things first: We need to understand small fact, if xor(a[0....i]) has appeared before at index j then it means xor(a[j+1.....i]) = 0 Another fact, if xor(a[i....j]) = 0 so this subarray will add (j - i - 1) to the answer.
Now say currently we are at index i and let xor([0...i]) = x.
Now say x has occurred 3 times previously at indices (i1, i2, i3)
our answer for i will be = (i - i1 - 1) + (i - i2 - 1) + (i - i3 - 1)
if you simplify this further you get f * i - (i1 + i2 + i3) - f = (i - 1) * f - (i1 + i2 + i3)
f = no. of times x has occurred previously.
(i1 + i2 + i3) = sum of all the indices where x has occurred previously.
class Solution {
public int countTriplets(int[] arr) {
int[] a = new int[arr.length + 1];
for (int i = 1; i < a.length; i ++) {
a[i] = arr[i - 1];
}
int n = a.length, res = 0, prefix = 0, c, t;
Map<Integer, Integer> count = new HashMap<>(), total = new HashMap<>();
for (int i = 0; i < n; ++i) {
prefix ^= a[i];
c = count.getOrDefault(prefix, 0);
t = total.getOrDefault(prefix, 0);
res += c * (i - 1) - t;
count.put(prefix, c + 1);
total.put(prefix, t + i);
}
return res;
}
}
Give the observation: For all pairs of i and k, where arr[i] ^ arr[i + 1] ^ ... ^ arr[k] = 0, then any j (i < j <= k) will be good to set as the answer (hint: proof by contradiction, if you cannot understand this trick immediately). So you just need to find all segments where XOR equals zero.
public int countTriplets(int[] arr) {
int ans = 0;
int length = arr.length;
for (int i = 0; i < length; i++) {
int xor = arr[i];
for (int j = i + 1; j < length; j++) {
xor ^= arr[j];
if (xor == 0) {
ans += (j - i);
}
}
}
return ans;
}