#1442

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Triplets That Can Form Two Arrays of Equal XOR

Efficiently count all triplets in an array where two subarrays formed by splitting have equal XOR using array scanning and hash lookup.

array hash table math bit manipulation prefix sum

Problem Statement

Given an integer array arr, your task is to count the number of triplets (i, j, k) where 0 <= i < j <= k < arr.length such that splitting arr into two subarrays arr[i..j-1] and arr[j..k] results in both having equal XOR values. The goal is to efficiently identify these triplets using array scanning and hash lookup techniques.

For example, with arr = [2,3,1,6,7], the triplets satisfying the condition are (0,1,2), (0,2,2), (2,3,4), and (2,4,4). Your solution must handle arrays of up to length 300 and values up to 10^8 while leveraging prefix XOR computations and hash maps to optimize counting.

Examples

Example 1

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

Output: 4

The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2

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

Output: 10

Example details omitted.

Constraints

1 <= arr.length <= 300
1 <= arr[i] <= 108

Solution Approach

Compute Prefix XOR

Maintain an array of prefix XOR values where prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]. This allows computing any subarray XOR in constant time, which is essential for efficiently comparing arr[i..j-1] and arr[j..k] without nested loops.

Use Hash Map to Track Prefix XOR Counts

Iterate through the array and store the frequency and cumulative indices of each prefix XOR value in a hash map. Whenever a repeated prefix XOR is encountered, it indicates that a subarray with zero XOR exists between previous occurrences and the current index, allowing multiple valid triplets to be counted efficiently.

Count Valid Triplets with Index Logic

For each repeated prefix XOR, calculate the number of triplets using the formula derived from previously stored counts and index sums. This approach avoids checking every triplet explicitly, leveraging the hash map to reduce complexity from O(n^3) to O(n).

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The solution achieves O(n) time because each element is processed once for prefix XOR and hash map updates. Space complexity is O(n) due to storing counts and index sums in the hash map, which grows linearly with unique prefix XOR values.

What Interviewers Usually Probe

Focus on prefix XOR computation to compare subarrays quickly.
Consider hash map accumulation to avoid triple nested loops.
Watch for overlapping subarrays and proper index handling.

Common Pitfalls or Variants

Common pitfalls

Forgetting that XOR of a subarray arr[i..j] can be computed using prefix XOR in O(1).
Miscounting triplets when multiple previous prefix XOR values exist at different indices.
Incorrectly handling i, j, k constraints leading to invalid subarrays.

Follow-up variants

Count quadruplets where splitting arr into three consecutive subarrays yields equal XORs.
Find all subarrays of length >= 2 with XOR zero without restricting to triplets.
Modify the array to allow negative numbers and still count valid triplets.

FAQ

What is the best approach to solve Count Triplets That Can Form Two Arrays of Equal XOR?

Use prefix XOR and a hash map to track previous XOR values and their indices, allowing efficient O(n) counting of all valid triplets.

Can this problem be solved without a hash map?

Yes, but a naive solution would require triple nested loops with O(n^3) time, which is inefficient for larger arrays.

Why is prefix XOR important for this problem?

Prefix XOR allows constant-time computation of any subarray XOR, which is essential for comparing subarrays arr[i..j-1] and arr[j..k] efficiently.

How do overlapping subarrays affect counting triplets?

Overlapping subarrays can produce multiple valid triplets for the same XOR value, so tracking cumulative indices is crucial to avoid undercounting.

Is this approach applicable to arrays with negative numbers?

Yes, the prefix XOR and hash map method works for negative numbers, but care must be taken with bitwise operations in languages that handle signed integers differently.

terminal

Solution

Solution 1: Enumeration

According to the problem description, to find triplets $(i, j, k)$ that satisfy $a = b$, which means $s = a \oplus b = 0$, we only need to enumerate the left endpoint $i$, and then calculate the prefix XOR sum $s$ of the interval $[i, k]$ with $k$ as the right endpoint. If $s = 0$, then for any $j \in [i + 1, k]$, the condition $a = b$ is satisfied, meaning $(i, j, k)$ is a valid triplet. There are $k - i$ such triplets, which we can add to our answer.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1248 count number of nice subarrays #1177 can make palindrome from substring #996 number of squareful arrays