Count triplets that can form two arrays of equal xor

Array Hash Table Math Bit Manipulation Prefix Sum

84.8% acceptance

Feb 25, 2026

2025

138

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_triplets(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] ^ arr[i]; }
    let mut count = 0;
    for i in 0..n {
      for k in i+1..n {
        if prefix[i] == prefix[k+1] {
          count += (k - i) as i32;
        }
      }
    }
    count
  }
}