Count Triplets That Can Form Two Arrays of Equal XOR Solution
Count Triplets That Can Form Two Arrays of Equal XOR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Triplets That Can Form Two Arrays of Equal XOR is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Bit Manipulation, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array arr, count the triples (i, j, k) with 0 <= i < j <= k < arr.length such that
a = arr[i] XOR arr[i+1] XOR … XOR arr[j-1]b = arr[j] XOR arr[j+1] XOR … XOR arr[k]
and a == b.
Example 1
Input: arr = [2,3,1,6,7]
Output: 4
Example 2
Input: arr = [1,1,1,1,1]
Output: 10
Example 3
Input: arr = [5]
Output: 0
Constraints
1 <= arr.length <= 401 <= arr[i] <= 100000000
Hints for Count Triplets That Can Form Two Arrays of Equal XOR
Hint 1
a == bis the same asa XOR b == 0, which is the XOR of the whole span fromitok.Hint 2
With prefix XORs, that condition becomes
prefix[i] == prefix[k + 1]— andjdrops out entirely.Hint 3
For each such
(i, k)pair, anyjin(i, k]works, so it contributesk - itriples.
How to solve Count Triplets That Can Form Two Arrays of Equal XOR
a == b iff a ^ b == 0, which is the XOR of the whole span arr[i..k]; with prefix XORs that is prefix[i] == prefix[k+1], and any j in (i, k] works — k - i choices.
Approach
- Build
prefix[t] = arr[0] ^ … ^ arr[t-1]. - For each
i < kwithprefix[i] == prefix[k+1], addk - i.
Why it works
The condition on (i, j, k) collapses to a condition on (i, k) alone, and j ranges freely over the interior positions.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- An O(n) version groups equal prefix values and sums index differences in bulk.
Reference solution
Python
def countTriplets(arr) -> int:
n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] ^ arr[i]
count = 0
for i in range(n):
for k in range(i + 1, n):
if prefix[i] == prefix[k + 1]:
count += k - i
return countJava
public static int countTriplets(int[] arr) {
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i];
int count = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (prefix[i] == prefix[k + 1]) count += k - i;
}
}
return count;
}C++
int countTriplets(vector<int>& arr) {
int n = (int) arr.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i];
int count = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (prefix[i] == prefix[k + 1]) count += k - i;
}
}
return count;
}JavaScript
var countTriplets = function(arr) {
const n = arr.length;
const prefix = [0];
for (let i = 0; i < n; i++) prefix.push(prefix[i] ^ arr[i]);
let count = 0;
for (let i = 0; i < n; i++) {
for (let k = i + 1; k < n; k++) {
if (prefix[i] === prefix[k + 1]) count += k - i;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets