⚡Flashcard Drill➔
NeetCode #873LC-1442MediumBit Manipulation
← Back to All Problems

#873 · #1442 · Count Triplets That Can Form Two Arrays of Equal XOR(形成两个异或相等数组的三元组数目)

📌 Problem Statement & Constraints

Given an array arr, count the triplets (i, j, k) with i < j <= k such that the XOR of arr[i..j-1] equals the XOR of arr[j..k]. Constraints: 1 <= arr.length <= 300, 1 <= arr[i] <= 10^8.

💡 Core Algorithmic Approaches

  1. Let prefix[p] be the XOR of the first p elements. The two window XORs are equal exactly when prefix[i] == prefix[q] where q = k + 1.
  2. For a fixed pair i < q with equal prefix values, every j with i < j <= k works, giving q - i - 1 valid triplets.
  3. So the answer is the sum of q - i - 1 over all pairs of equal prefix values.
  4. An O(n) refinement groups prefix values and tracks, for each, the running count and the sum of indices seen so far.

💻 Benchmark Python3 Implementation

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i, x in enumerate(arr):
            prefix[i + 1] = prefix[i] ^ x
        count = 0
        for i in range(n + 1):
            for q in range(i + 1, n + 1):
                if prefix[i] == prefix[q]:
                    count += q - i - 1      # number of valid j in between
        return count


# O(n) variant: for each prefix value, track its count and the sum of its indices
class Solution2:
    def countTriplets(self, arr: List[int]) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)          # prefix value -> occurrences so far
        total = defaultdict(int)        # prefix value -> sum of indices so far
        prefix = 0
        res = 0
        for q in range(len(arr) + 1):
            # pairs (i, q) with equal prefix contribute q - i - 1
            res += cnt[prefix] * (q - 1) - total[prefix]
            cnt[prefix] += 1
            total[prefix] += q
            if q < len(arr):
                prefix ^= arr[q]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2) for the pair enumeration; O(n) for the grouped variant.
💾 Space Complexity
O(n): the prefix array, or the two maps in the linear variant.

⚠️ Interview Pitfalls & Follow-ups

  • Getting the boundary wrong: the second window starts at j, so the equal-prefix condition involves prefix[k + 1], not prefix[k].
  • Counting only j == i + 1: every j strictly between i and k + 1 works, which is q - i - 1 choices.
  • Forgetting the empty prefix: prefix[0] = 0 must be included, otherwise triplets starting at index 0 are missed.
  • Using the wrong contribution in the linear form: for a pair (i, q) the contribution is q - i - 1, so the running term is (q - 1) * count - sum_of_indices.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems