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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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:

1
2
3
4


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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
    }
}

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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.

Triples with Bitwise AND Equal To Zero Problem#

Problem#

Examples#

Solution#

Method 1 – Bitmask Counting with Hash Map#

Intuition#

Approach#

Code#

Complexity#