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
- Let
prefix[p]be the XOR of the firstpelements. The two window XORs are equal exactly whenprefix[i] == prefix[q]whereq = k + 1. - For a fixed pair
i < qwith equal prefix values, everyjwithi < j <= kworks, givingq - i - 1valid triplets. - So the answer is the sum of
q - i - 1over all pairs of equal prefix values. - 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 involvesprefix[k + 1], notprefix[k]. - Counting only
j == i + 1: everyjstrictly betweeniandk + 1works, which isq - i - 1choices. - Forgetting the empty prefix:
prefix[0] = 0must 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 isq - 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.