Triples with bitwise and equal to zero

Array Hash Table Bit Manipulation

60.0% acceptance

Feb 25, 2026

478

222

Given an integer array nums, return the number of AND triples. An AND triple is a triple of indices (i, j, k) such that: 0 <= i < nums.length 0 <= j < nums.length 0 <= k < nums.length nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_triplets(nums: Vec<i32>) -> i32 {
    let mut pair_and = vec![0i32; 1 << 16];
    for &a in &nums { for &b in &nums { pair_and[(a & b) as usize] += 1; } }
    let mut ans = 0;
    for &c in &nums {
      for v in 0..pair_and.len() {
        if v as i32 & c == 0 { ans += pair_and[v]; }
      }
    }
    ans
  }
}