Count Triplets That Can Form Two Arrays of Equal XOR
MedPrompt
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 <= 3001 <= arr[i] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through all possible combinations of indices i, j, and k that satisfy the condition 0 <= i < j <= k < arr.length. For each triplet, it calculates the XOR sums a (for subarray arr[i...j-1]) and b (for subarray arr[j...k]) and checks if they are equal. If they are, a counter is incremented.
Algorithm
- Initialize a variable
countto 0. - Use three nested loops to iterate through all possible triplets
(i, j, k)satisfying0 <= i < j <= k < arr.length. - The outer loop for
iruns from0ton-1. - The middle loop for
jruns fromi + 1ton-1. - The inner loop for
kruns fromjton-1. - Inside the loops, calculate
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]andb = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]. - To optimize, these XOR sums can be calculated incrementally within their respective loops.
- If
ais equal tob, increment thecount. - After all triplets have been checked, return
count.
Walkthrough
The brute-force method involves a straightforward, exhaustive search. We set up three nested loops to generate every valid triplet of indices (i, j, k). The outermost loop selects the starting index i, the second loop selects the split point j, and the innermost loop selects the ending index k. For each triplet, we must compute two separate XOR sums: a for the subarray from i to j-1, and b for the subarray from j to k. A naive implementation would calculate these sums from scratch each time, leading to an O(N^5) complexity. However, we can optimize this by calculating the XOR sums incrementally. For a fixed i, as j increases, we can update a. Similarly, for a fixed j, as k increases, we can update b. This optimization reduces the complexity to O(N^3), which is still computationally expensive but a significant improvement.
Complexity
Time
O(N^3), where N is the length of the array. The three nested loops for `i`, `j`, and `k` are the dominant factor in the runtime.
Space
O(1), as we only use a constant amount of extra space for variables to store loop indices, XOR sums, and the final count.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem's definition.
Requires no extra space beyond a few variables for loops and sums.
Cons
Highly inefficient due to its cubic time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms with stricter time limits for this problem size.
A key mathematical observation simplifies the problem significantly. The condition a == b, where a and b are XOR sums, is equivalent to a ^ b == 0. The expression a ^ b is the XOR sum of the entire subarray from i to k. Therefore, the problem is to find the number of triplets (i, j, k) where arr[i] ^ arr[i+1] ^ ... ^ arr[k] == 0.
For any pair of indices (i, k) where the XOR sum of arr[i...k] is 0, we can choose any j such that i < j <= k to form a valid triplet. The number of choices for j is k - i. This insight allows us to reframe the problem as finding all such (i, k) pairs and summing up the k - i values.
Algorithm
- Realize that
a == bis equivalent toa ^ b == 0. - The expression
a ^ bis the XOR sum of the entire subarray fromitok, i.e.,arr[i] ^ ... ^ arr[k]. - The problem reduces to finding pairs
(i, k)where the XOR sum ofarr[i...k]is 0. - For each such pair, any
jwithi < j <= kforms a valid triplet. The number of suchj's isk - i. - Initialize
count = 0. - Loop
ifrom0toarr.length - 1.- Initialize
current_xor = 0. - Loop
kfromitoarr.length - 1.- Update
current_xor ^= arr[k]. - If
current_xor == 0andk > i, addk - itocount.
- Update
- Initialize
- Return
count.
Walkthrough
This approach leverages the property of the XOR operation. Instead of iterating through i, j, and k, we only need to iterate through i and k. We use two nested loops: an outer loop for the start index i and an inner loop for the end index k.
For each i, we iterate k from i to the end of the array. We maintain a running XOR sum for the subarray arr[i...k]. If at any point this running XOR sum becomes zero, it means we've found a valid pair (i, k). For this pair, we know there are k - i possible values for j that will satisfy the original condition. We add this number, k - i, to our total count. This process is repeated for all possible start indices i.
Complexity
Time
O(N^2), due to the two nested loops required to check all possible subarrays `arr[i...k]`.
Space
O(1), as we only use a few variables for the loops, the running XOR sum, and the total count.
Trade-offs
Pros
Significantly more efficient than the O(N^3) brute-force approach.
The logic is still relatively straightforward and easy to implement.
Maintains O(1) space complexity.
Cons
While much better than brute force, the O(N^2) complexity might still be too slow for very large input arrays (though it passes for the given constraints).
This is the most optimal approach, achieving a linear time complexity. It builds upon the simplified condition XOR(i, k) == 0 and utilizes a prefix XOR array (or a running prefix XOR value) to identify valid (i, k) pairs in a single pass. The core idea is that XOR(i, k) == 0 is equivalent to prefix_xor[k+1] == prefix_xor[i]. By storing the counts and indices of previously seen prefix XOR values in hash maps, we can quickly calculate the number of new triplets formed at each step.
Algorithm
- The condition
XOR(i, k) == 0can be checked efficiently using prefix XORs. Letp[x] = arr[0] ^ ... ^ arr[x-1]. - Then
XOR(i, k) = p[k+1] ^ p[i]. The condition becomesp[k+1] == p[i]. - We need to calculate
sum(k - i)over all pairs(i, k)wherep[k+1] == p[i]. - This can be rewritten as
sum(c * k - sum_of_indices), wherecis the count of previous occurrences of a prefix XOR value andsum_of_indicesis the sum of their indices. - Initialize
total_triplets = 0,prefix_xor = 0. - Use two HashMaps:
countMapto store frequencies of prefix XORs, andindexSumMapto store the sum of indices for each prefix XOR. - Initialize
countMapwith{0: 1}andindexSumMapwith{0: -1}to handle subarrays starting at index 0. - Loop
kfrom0ton-1:- Update
prefix_xor ^= arr[k]. - If
prefix_xoris incountMap, retrieve its countcand sum of previousk'ss. - Add
c * k - s - ctototal_triplets. - Update
countMapandindexSumMapwith the currentprefix_xorand indexk.
- Update
- Return
total_triplets.
Walkthrough
We iterate through the array using a single loop with index k. We maintain a running prefixXor value. The goal is to find, for each k, the sum of k - i for all i < k such that XOR(i, k) == 0. This is equivalent to finding i where prefix_xor[i] == prefix_xor[k+1].
To do this efficiently, we use two hash maps. countMap stores how many times we've seen each prefix XOR value. indexSumMap stores the sum of the indices k at which each prefix XOR value occurred.
As we iterate through k from 0 to n-1, we update prefixXor. We then look up this prefixXor in our maps. If we've seen this value c times before at indices k_1, k_2, ..., k_c, we can form c new valid ranges ending at the current k. The start index i for a range found at a previous k_r is k_r + 1. The number of triplets added is sum(k - (k_r + 1)), which simplifies to c * k - sum(k_r) - c. We retrieve c and sum(k_r) from our maps, calculate the contribution, and add it to our total. Finally, we update the maps with the prefixXor and the current index k.
Complexity
Time
O(N), where N is the length of the array. We iterate through the array once, and all hash map operations (put, get) take, on average, O(1) time.
Space
O(N) in the worst case. If all prefix XOR sums are distinct, the hash maps will store N entries. In the best case (e.g., all elements are 0), the space is O(1).
Trade-offs
Pros
Most efficient solution with O(N) time complexity.
Solves the problem in a single pass through the array.
Cons
The logic is more complex and less intuitive than the previous approaches.
Requires additional space for the hash maps, which can be up to O(N) in the worst case.
Solutions
Solution
class Solution {public int countTriplets(int[] arr) { int n = arr.length; int[] pre = new int[n + 1]; for (int i = 0; i < n; ++i) { pre[i + 1] = pre[i] ^ arr[i]; } int ans = 0; for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j; k < n; ++k) { int a = pre[j] ^ pre[i]; int b = pre[k + 1] ^ pre[j]; if (a == b) { ++ans; } } } } return ans; }}class Solution {public: int countTriplets(vector<int> &arr) { int n = arr.size(); vector<int> pre(n + 1); for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] ^ arr[i]; int ans = 0; for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j; k < n; ++k) { int a = pre[j] ^ pre[i], b = pre[k + 1] ^ pre[j]; if (a == b) ++ans; } } } return ans; }};class Solution: def countTriplets(self, arr: List[int]) -> int: n = len(arr) pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] ^ arr[i] ans = 0 for i in range(n - 1): for j in range(i + 1, n): for k in range(j, n): a, b = pre[j] ^ pre[i], pre[k + 1] ^ pre[j] if a == b: ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.