Count triplets with even xor set bits i

Array Bit Manipulation

83.1% acceptance

Mar 31, 2026

Given three integer arrays a, b, and c, return the number of triplets (a[i], b[j], c[k]), such that the bitwise XOR of the elements of each triplet has an even number of set bits.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn triplet_count(a: Vec<i32>, b: Vec<i32>, c: Vec<i32>) -> i32 {
    let count_even = |v: &Vec<i32>| v.iter().filter(|&&x| x.count_ones() % 2 == 0).count() as i64;
    let ea = count_even(&a);
    let oa = a.len() as i64 - ea;
    let eb = count_even(&b);
    let ob = b.len() as i64 - eb;
    let ec = count_even(&c);
    let oc = c.len() as i64 - ec;
    (ea * eb * ec + ea * ob * oc + oa * eb * oc + oa * ob * ec) as i32
  }
}