982. Triples with Bitwise AND Equal To Zero

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

  • 0 <= i < A.length
  • 0 <= j < A.length
  • 0 <= k < A.length
  • A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

 

Example 1:

Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

 

Note:

  1. 1 <= A.length <= 1000
  2. 0 <= A[i] < 2^16

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn count_triplets(a: Vec<i32>) -> i32 {
        let n = a.len();
        let mut hm: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            for j in 0..n {
                *hm.entry(a[i] & a[j]).or_default() += 1;
            }
        }
        let mut res = 0;
        for i in 0..n {
            for (&k, &v) in hm.iter() {
                if a[i] & k == 0 {
                    res += v;
                }
            }
        }
        res as i32
    }
}

#[test]
fn test() {
    let a = vec![2, 1, 3];
    let res = 12;
    assert_eq!(Solution::count_triplets(a), res);
}

Having problems with this solution? Click here to submit an issue on github.