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.
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; }}Video 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.