Count Triplets That Can Form Two Arrays of Equal XOR

Medium
435.

Count Triplets That Can Form Two Arrays of Equal XOR

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.

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 <= 40
  • 1 <= arr[i] <= 100000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var countTriplets = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 1 <= arr[i] <= 100000000

Hints for Count Triplets That Can Form Two Arrays of Equal XOR

  1. Hint 1

    a == b is the same as a XOR b == 0, which is the XOR of the whole span from i to k.

  2. Hint 2

    With prefix XORs, that condition becomes prefix[i] == prefix[k + 1] — and j drops out entirely.

  3. Hint 3

    For each such (i, k) pair, any j in (i, k] works, so it contributes k - i triples.

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

  1. Build prefix[t] = arr[0] ^ … ^ arr[t-1].
  2. For each i < k with prefix[i] == prefix[k+1], add k - 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 count

Java

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