Course4all

Count Triplets That Can Form Two Arrays of Equal XOR

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

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

  1. Use three nested loops for i, j, and k.
  2. In the innermost loop, calculate XOR for a and b.
  3. 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)(i, k) such that P[i]==P[k+1]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==ba == b is equivalent to arr[i]⊕...⊕arr[k]=0arr[i] \oplus ... \oplus arr[k] = 0. Using prefix XOR array PP where P[x]=arr[0]⊕...⊕arr[x−1]P[x] = arr[0] \oplus ... \oplus arr[x-1], the XOR of arr[i...k]arr[i...k] is P[k+1]⊕P[i]P[k+1] \oplus P[i]. We need P[k+1]==P[i]P[k+1] == P[i]. If found, all j∈(i,k]j \in (i, k] are valid.

Thought Process

  1. Calculate prefix XOR array prefix.
  2. Iterate through all pairs (i,k)(i, k) where i<ki < 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMissing Number
Next Question →Gray Code