Count Triplets That Can Form Two Arrays of Equal XOR

Master this topic with zero to advance depth.

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 a = arr[i] ^ ... ^ arr[j - 1] and b = arr[j] ^ ... ^ arr[k]. Return the number of triplets (i, j, k) such that a == b.

Medium

Examples

Input: arr = [2,3,1,6,7]
Output: 4

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

Approach 1

Level I: Brute Force (O(N^3))

Intuition

Iterate through all possible combinations of i, j, and k. Calculate a and b for each triplet and check if they are equal.

Thought Process

Use three nested loops for i, j, and k.
In the innermost loop, calculate XOR for a and b.
If a == b, increment count.

Pattern: Triple Nested Iteration

⏱ O(N^3) or O(N^4) - Depending on how XOR is calculated.💾 O(1) - Constant space.

java

public class Solution {
    public int countTriplets(int[] arr) {
        int count = 0, n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j; k < n; k++) {
                    int a = 0, b = 0;
                    for (int x = i; x < j; x++) a ^= arr[x];
                    for (int x = j; x <= k; x++) b ^= arr[x];
                    if (a == b) count++;
                }
            }
        }
        return count;
    }
}

Approach 2

Level II: Prefix XOR with Hash Map

Intuition

We seek $(i, k)$ such that $P[i] == P[k+1]$ . Instead of a nested loop, we can use a hash map to store the indices (or counts and sum of indices) where each prefix XOR has occurred.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length, res = 0, prefix = 0;
        Map<Integer, Integer> count = new HashMap<>(), total = new HashMap<>();
        count.put(0, 1);
        for (int i = 0; i < n; i++) {
            prefix ^= arr[i];
            res += count.getOrDefault(prefix, 0) * i - total.getOrDefault(prefix, 0);
            count.put(prefix, count.getOrDefault(prefix, 0) + 1);
            total.put(prefix, total.getOrDefault(prefix, 0) + i + 1);
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Prefix XOR)

Intuition

As shown in the logic representation, $a == b$ is equivalent to $arr[i] \oplus ... \oplus arr[k] = 0$ . Using prefix XOR array $P$ where $P[x] = arr[0] \oplus ... \oplus arr[x-1]$ , the XOR of $arr[i...k]$ is $P[k+1] \oplus P[i]$ . We need $P[k+1] == P[i]$ . If found, all $j \in (i, k]$ are valid.

Thought Process

Calculate prefix XOR array prefix.
Iterate through all pairs $(i, k)$ $(i, k)$ where $i < k$ $i < k$ :
- If prefix[i] == prefix[k+1]:
  - The number of valid j's is k - i.
  - Add k - i to total.

Pattern: Subarray XOR Frequency

⏱ O(N^2) - Iterate through all possible $(i, k)$ pairs.💾 O(N) - Storage for prefix XOR array.

Detailed Dry Run

arr = [2, 3, 1, 6, 7] Prefix: [0, 2, 1, 0, 6, 1] Pairs with equal prefix values:

P[0] and P[3]: (i=0, k=2). count += 2-0 = 2 triplets.
P[2] and P[5]: (i=2, k=4). count += 4-2 = 2 triplets. Total: 2 + 2 = 4.

java

public class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length, count = 0;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i];
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                if (prefix[i] == prefix[k + 1]) {
                    count += (k - i);
                }
            }
        }
        return count;
    }
}

← Previous QuestionMissing Number

Next Question →Gray Code

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.