Skip to main content
Talentd

Count Triplets That Can Form Two Arrays of Equal XOR - Solution & Explanation

MediumArrayHash TableMathBit Manipulation11 min readAsked at: Meta, Google
Practice this problem

Problem Statement

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let's define a and b as follows:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

 

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: 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

 

Constraints:

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

Approach Overview

Problem Overview: Given an integer array arr, count triplets (i, j, k) where 0 ≤ i < j ≤ k < n and the XOR of arr[i..j-1] equals the XOR of arr[j..k]. The task reduces to identifying segments where two adjacent subarrays share the same XOR value.

Approach 1: Utilize Prefix XOR (O(n2) time, O(n) space)

Compute a prefix XOR array where px[i] stores the XOR of elements from index 0 to i-1. Using the XOR identity a ^ a = 0, the condition arr[i..j-1] == arr[j..k] becomes px[i] == px[k+1]. Iterate over all pairs (i, k) and when the prefix XOR values match, every index between them can serve as a valid split point j. Each match contributes k - i triplets. This approach directly leverages properties of prefix sum-style preprocessing with XOR operations and is easy to implement but requires a quadratic scan.

Approach 2: Optimized Prefix XOR Count (O(n) time, O(n) space)

Track how often each prefix XOR value appears while scanning the array once. Maintain two hash maps: one for frequency of each prefix XOR and another for the total index sum where that XOR occurred. When the current prefix XOR repeats, it means earlier positions can form valid segments with the current index. The number of new triplets depends on how many times that XOR appeared and the distance between indices. Each step performs constant-time hash lookups, turning the quadratic search into a linear pass. This technique combines hash table counting with XOR prefix properties from bit manipulation.

Recommended for interviews: The optimized prefix XOR counting approach is what most interviewers expect. The quadratic prefix XOR version shows that you understand the mathematical reduction px[i] == px[k+1]. The linear hash‑map solution demonstrates deeper algorithmic insight and reduces the complexity to O(n), which is the optimal bound for scanning the array.

Approach 1: Approach 1: Utilize Prefix XOR

To find the number of triplets, we can utilize prefix XOR which makes checking if two subarrays have equal XOR efficient. For any indices i, j, k in the array, if the XOR from i to j-1 equals the XOR from j to k, we have a valid triplet. Using prefix XOR allows us to calculate this in constant time.

We compute the prefix XOR of the array where prefix[i] is the XOR from the start of the array to index i. For each pair of indices (i, k), if (prefix[i-1] == prefix[k]), then for all j where i <= j <= k, (i, j, k) will form a valid triplet.

In this Python solution, we use a prefix array to store the prefix XOR of the elements. We iterate over all possible pairs (i, k) and check if the XOR from the start to i-1 equals the XOR from the start to k. For every match, we then count the valid j indices that form a triplet.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops.
Space Complexity: O(n), due to the storage of the prefix array.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Prefix XOR Count

This approach optimizes the first one by reducing redundant checks and efficiently calculating the number of valid triplet indices.

As we calculate the prefix XOR, we maintain a hashmap (or dictionary) which helps in counting valid j values directly, reducing the nested loop complexity by using suffix array observations.

In the Java solution, we use hashmaps to store the frequency and counts of the prefix XORs. This allows us to calculate the number of valid j indices without needing to iterate exhaustively, leveraging hash lookups instead.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop.
Space Complexity: O(n), primarily due to hashmap storage.

Try this approach in the editor →

Approach 3: 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.

After the enumeration is complete, we return the answer.

The time complexity is O(n^2), where n is the length of the array arr. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Utilize Prefix XOR

Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops.
Space Complexity: O(n), due to the storage of the prefix array.

Approach 2: Optimized Prefix XOR Count

Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop.
Space Complexity: O(n), primarily due to hashmap storage.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix XOR Pair EnumerationO(n^2)O(n)Useful for understanding the XOR property and during initial reasoning in interviews
Optimized Prefix XOR with Hash CountingO(n)O(n)Best general solution; handles large arrays efficiently with constant‑time hash lookups

Video Solution

Count Triplets That Can Form Two Arrays of Equal XOR | Leetcode 1442 | codestorywithMIK • codestorywithMIK • 11,047 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Triplets That Can Form Two Arrays of Equal XOR easy or hard?
The problem is rated Medium because the key difficulty is recognizing the XOR identity that converts the condition into prefix XOR equality. Once that insight is clear, the optimized solution using hash maps becomes a straightforward linear scan.
Count Triplets That Can Form Two Arrays of Equal XOR Python/Java solution
Python solutions typically use dictionaries to store prefix XOR counts and index totals, while Java and C++ implementations use HashMap or unordered_map. All versions follow the same logic: compute running XOR, check previous occurrences, and accumulate triplet counts in O(n) time.
How to solve Count Triplets That Can Form Two Arrays of Equal XOR in O(n)?
Compute a running prefix XOR while iterating through the array. Store how many times each prefix XOR value has appeared and the total of their indices. When the same XOR value occurs again at index k, earlier matches indicate subarrays whose XOR cancels out, allowing you to count valid triplets in constant time using the stored counts and index sums.
What is the best approach for Count Triplets That Can Form Two Arrays of Equal XOR?
The optimal approach uses prefix XOR combined with hash map counting. While scanning the array, track how many times each prefix XOR value appears and the sum of their indices. When the same prefix XOR appears again, earlier positions form valid triplets with the current index. This reduces the problem to O(n) time and O(n) space.
Is Count Triplets That Can Form Two Arrays of Equal XOR asked at Google/Amazon/Meta?
Variants of prefix XOR and subarray XOR problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often use this problem to test understanding of XOR properties, prefix techniques, and hash map optimizations.
What data structure is used in Count Triplets That Can Form Two Arrays of Equal XOR?
The optimized solution relies on a hash table (hash map) to store prefix XOR frequencies and index sums. Combined with prefix XOR computation, this allows constant-time lookups to determine how many earlier positions can form valid triplets with the current index.
What is the time complexity of Count Triplets That Can Form Two Arrays of Equal XOR?
The optimal algorithm runs in O(n) time using prefix XOR with hash map aggregation. A simpler implementation using prefix XOR and checking all (i, k) pairs runs in O(n^2) time. Both approaches use O(n) auxiliary space for prefix values or frequency maps.

Ready to solve this problem?

Practice Count Triplets That Can Form Two Arrays of Equal XOR with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find The Original Array of Prefix Xor