LeetCode 982: Triples with Bitwise AND Equal To Zero

Problem Restatement

We are given an integer array nums.

We need to count the number of ordered triples of indices (i, j, k) such that:

nums[i] & nums[j] & nums[k] == 0

The indices may repeat. For example, (0, 0, 1) is allowed.

The triple is ordered, so (0, 1, 2) and (1, 0, 2) are counted as different triples if both satisfy the condition.

The official constraints are:

Source: LeetCode problem statement.

Input and Output

Function shape:

def countTriplets(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [2, 1, 3]

In binary:

2 = 10
1 = 01
3 = 11

We need ordered triples where the bitwise AND becomes 0.

There are 12 valid triples.

Answer:

12

Example 2:

nums = [0]

The only ordered triple is:

(0, 0, 0)

And:

0 & 0 & 0 == 0

Answer:

1

First Thought: Check Every Triple

The direct solution is to try every ordered triple.

class Solution:
    def countTriplets(self, nums: list[int]) -> int:
        n = len(nums)
        answer = 0

        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if nums[i] & nums[j] & nums[k] == 0:
                        answer += 1

        return answer

This follows the problem statement exactly.

Problem With Brute Force

The brute force solution checks n^3 triples.

Since nums.length can be 1000, this can require up to:

1000^3 = 1,000,000,000

checks.

That is too slow.

We need to reuse intermediate bitwise AND results.

Key Insight

Bitwise AND is associative:

(nums[i] & nums[j]) & nums[k] == nums[i] & nums[j] & nums[k]

So instead of checking every triple directly, we can first count all pairwise AND results.

For every ordered pair (i, j), compute:

pair = nums[i] & nums[j]

Store how many pairs produce each pair value.

Then for each num in nums, every pair value pair such that:

pair & num == 0

forms valid triples.

If count[pair] = c, then this contributes c triples for the current num.

This changes the problem from counting triples directly to counting pair results first.

Algorithm

Create a frequency map pair_count.

For every ordered pair (a, b) in nums:

1. Compute a & b.
2. Increment its count in pair_count.

Then count valid triples:

1. For every value pair in pair_count.
2. For every number num in nums.
3. If pair & num == 0, add pair_count[pair] to the answer.

Correctness

Every ordered triple (i, j, k) can be split into an ordered pair (i, j) and a third index k.

For the pair (i, j), the algorithm computes:

pair = nums[i] & nums[j]

The triple is valid exactly when:

pair & nums[k] == 0

The first phase counts how many ordered pairs produce each possible pair value. Therefore, when the second phase finds that pair & nums[k] == 0, all ordered pairs that produced that same pair value form valid triples with the current k.

The algorithm adds exactly that number of pairs.

Every valid ordered triple is counted once: when the pair value from its first two indices is considered with its third value.

No invalid triple is counted, because the algorithm adds a pair count only when the final bitwise AND is zero.

Therefore, the algorithm returns the correct number of ordered triples.

Complexity

Let n = len(nums) and let m be the number of distinct pairwise AND results.

Since nums[i] < 2^16, there are at most 2^16 possible AND values.

So m <= 2^16.

Implementation

from collections import Counter

class Solution:
    def countTriplets(self, nums: list[int]) -> int:
        pair_count = Counter()

        for a in nums:
            for b in nums:
                pair_count[a & b] += 1

        answer = 0

        for pair, count in pair_count.items():
            for num in nums:
                if pair & num == 0:
                    answer += count

        return answer

Code Explanation

We store pairwise AND frequencies:

pair_count = Counter()

Then compute all ordered pairs:

for a in nums:
    for b in nums:
        pair_count[a & b] += 1

This includes repeated indices and ordered pairs, which matches the problem.

For example, both (i, j) and (j, i) are counted.

Then we test each pair result against each third number:

for pair, count in pair_count.items():
    for num in nums:

If the final AND is zero:

if pair & num == 0:

then all pairs represented by count are valid with this num:

answer += count

Finally, return the total:

return answer

Testing

def run_tests():
    s = Solution()

    assert s.countTriplets([2, 1, 3]) == 12
    assert s.countTriplets([0]) == 1
    assert s.countTriplets([0, 0]) == 8
    assert s.countTriplets([1]) == 0
    assert s.countTriplets([1, 2]) == 6

    print("all tests passed")

run_tests()