[Leetcode] Problem 1442 - Count Triplets That Can Form Two Arrays of Equal XOR

Posted on | In ,

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

No.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)

No.2

Input: arr = [1,1,1,1,1]

Output: 10

No.3

Input: arr = [2,3]

Output: 0

No.4

Input: arr = [1,3,5,7,9]

Output: 3

No.5

Input: arr = [7,11,12,9,5,2,7,17,22]

Output: 8

Constraints

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// X[i] = X[j] = X[k] = X[n]
// ans = (j - i - 1) +
//       (k - i - 1) + (k - j - 1) +
//       (n - i - 1) + (n - j - 1) + (n - k - 1)
//     = (i * 0 - 0) + (j * 1 - (i + 1)) + (k * 2 - (i + 1 + j + 1)) + (n * 3 - (i + 1 + j + 1 + k + 1))
// ans += freq[X] * i - sum[X]
public int countTriplets(int[] arr) {
    int result = 0;
    Map<Integer, Integer> sum = new HashMap<>();
    Map<Integer, Integer> freq = new HashMap<>();
    int X = 0;
    freq.put(0, 1);

    for (int i = 0; i < arr.length; i++) {
        X ^= arr[i];
        int f = freq.getOrDefault(X, 0);
        int s = sum.getOrDefault(X, 0);
        result += f * i - s;
        sum.put(X, s + i + 1);
        freq.put(X, f + 1);
    }

    return result;
}