Triples with Bitwise AND Equal To Zero Problem

Problem

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.

Examples

Example 1:

Input:
nums = [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

Example 2:

Input:
nums = [0,0,0]
Output:
 27

Solution

Method 1 – Bitmask Counting with Hash Map

Intuition

To count the number of triples (i, j, k) such that nums[i] & nums[j] & nums[k] == 0, we can precompute the count of all possible pairwise ANDs, then for each number, count how many pairs can form a triple with it such that the AND is zero. This leverages the small range of possible AND results (since nums[i] <= 2^16).

Approach

1. For all pairs (i, j), compute nums[i] & nums[j] and count their frequencies in a hash map.
2. For each number x in nums, for all possible mask values, if x & mask == 0, add the count of mask to the answer.
3. Return the total count.

Code

C++

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int a : nums) for (int b : nums) cnt[a & b]++;
        int ans = 0;
        for (int x : nums) {
            for (auto& [mask, c] : cnt) {
                if ((x & mask) == 0) ans += c;
            }
        }
        return ans;
    }
};

Go

func countTriplets(nums []int) int {
    cnt := map[int]int{}
    for _, a := range nums {
        for _, b := range nums {
            cnt[a&b]++
        }
    }
    ans := 0
    for _, x := range nums {
        for mask, c := range cnt {
            if x&mask == 0 {
                ans += c
            }
        }
    }
    return ans
}

Java

class Solution {
    public int countTriplets(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int a : nums) for (int b : nums) cnt.put(a & b, cnt.getOrDefault(a & b, 0) + 1);
        int ans = 0;
        for (int x : nums) {
            for (int mask : cnt.keySet()) {
                if ((x & mask) == 0) ans += cnt.get(mask);
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countTriplets(nums: IntArray): Int {
        val cnt = mutableMapOf<Int, Int>()
        for (a in nums) for (b in nums) cnt[a and b] = cnt.getOrDefault(a and b, 0) + 1
        var ans = 0
        for (x in nums) {
            for ((mask, c) in cnt) {
                if (x and mask == 0) ans += c
            }
        }
        return ans
    }
}

Python

def countTriplets(nums: list[int]) -> int:
    from collections import Counter
    cnt = Counter(a & b for a in nums for b in nums)
    ans = 0
    for x in nums:
        for mask, c in cnt.items():
            if x & mask == 0:
                ans += c
    return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn count_triplets(nums: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for &a in &nums {
            for &b in &nums {
                *cnt.entry(a & b).or_insert(0) += 1;
            }
        }
        let mut ans = 0;
        for &x in &nums {
            for (&mask, &c) in &cnt {
                if x & mask == 0 {
                    ans += c;
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countTriplets(nums: number[]): number {
        const cnt = new Map<number, number>();
        for (const a of nums) for (const b of nums) {
            const ab = a & b;
            cnt.set(ab, (cnt.get(ab) ?? 0) + 1);
        }
        let ans = 0;
        for (const x of nums) {
            for (const [mask, c] of cnt.entries()) {
                if ((x & mask) === 0) ans += c;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2 + n*m), where n is the length of nums and m is the number of unique AND results (at most 2^16).
• 🧺 Space complexity: O(m), for the hash map.