Count Triplets That Can Form Two Arrays of Equal XOR

Reduces to counting (i, k) pairs with prefix XOR equal — sum (k - i) for each such pair.

Medium

Time O(n^2) simple Space O(n)

LeetCode

May 16, 2026 4 min read

Problem#

Count triplets (i, j, k) with i < j <= k such that XOR(arr[i..j-1]) == XOR(arr[j..k]).

Examples#

[2,3,1,6,7] → 4.
[1,1,1,1,1] → 10.

Constraints#

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

Approach#

Let p be the prefix-XOR array (p[0] = 0). The condition reduces to p[i] == p[k+1]. For any such pair (i, k), every j with i < j <= k works — that’s k - i triplets.

Solution#

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        vector<int> p(n + 1, 0);
        for (int i = 0; i < n; ++i) p[i + 1] = p[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i <= n; ++i)
            for (int k = i + 1; k <= n; ++k)
                if (p[i] == p[k]) ans += (k - i - 1);
        return ans;
    }
};

func countTriplets(arr []int) int {
    n := len(arr)
    p := make([]int, n+1)
    for i := 0; i < n; i++ {
        p[i+1] = p[i] ^ arr[i]
    }
    ans := 0
    for i := 0; i <= n; i++ {
        for k := i + 1; k <= n; k++ {
            if p[i] == p[k] {
                ans += k - i - 1
            }
        }
    }
    return ans
}

from typing import List

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        p = [0] * (n + 1)
        for i in range(n):
            p[i + 1] = p[i] ^ arr[i]
        ans = 0
        for i in range(n + 1):
            for k in range(i + 1, n + 1):
                if p[i] == p[k]:
                    ans += k - i - 1
        return ans

function countTriplets(arr) {
    const n = arr.length;
    const p = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) p[i + 1] = p[i] ^ arr[i];
    let ans = 0;
    for (let i = 0; i <= n; i++) {
        for (let k = i + 1; k <= n; k++) {
            if (p[i] === p[k]) ans += k - i - 1;
        }
    }
    return ans;
}

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

function countTriplets(arr: number[]): number {
    const n = arr.length;
    const p: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) p[i + 1] = p[i] ^ arr[i];
    let ans = 0;
    for (let i = 0; i <= n; i++) {
        for (let k = i + 1; k <= n; k++) {
            if (p[i] === p[k]) ans += k - i - 1;
        }
    }
    return ans;
}

Editorial#

XOR(a..b) reduces to p[a] ^ p[b+1]. The two halves being equal means their combined XOR is 0, i.e., p[i] == p[k+1]. Once that holds, the split point j is free anywhere in (i, k], contributing k - i triplets.

Complexity#

Time: O(n^2) straightforward; O(n) with a hashmap tracking last positions and counts.
Space: O(n).

Concept revision#

Find the Longest Substring Having Vowels in Even Counts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#