Solution: Triples with Bitwise AND Equal To Zero

Statement

You’re given an array of integers called nums. Your task is to count how many triplets of indexes (i, j, k) satisfy the condition nums[i] & nums[j] & nums[k] == 0, where & is the bitwise AND operator and $0 \leq$ i$,$ j$,$ k $\leq$ nums.length.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $0 \leq$ nums[i] $\leq 2^{10}$

Solution

The essence of this solution lies in breaking the problem into two phases. First, precompute and count all possible pairwise bitwise AND results of the array elements, storing their frequencies in a hash map. Then, check how many of these precomputed results produce zero for each number in the array when ANDed with that number. If they do, add their frequency to the total count, since each matching pair combined with the current number forms a valid triplet. This reduces the problem from a brute-force $O(n^3)$ search to a much more efficient counting strategy.

Using the intuition above, we implement the algorithm as follows:

1. Create a hash map, counts, to store the frequency of all possible pairwise bitwise AND results from the array.

2. Loop through all pairs of integers in the nums array:

   1. Compute the bitwise AND of nums[i] and nums[j] and increment the frequency of this result in the counts map.

3. Initialize a variable, result, with $0$ to hold the total number of valid triplets whose bitwise AND equals zero.

4. For each element nums[i] in the array:

   1. Iterate through each $key - value$ pair in counts:

      1. If the result of nums[i] AND $key$ equals 0, then the pair that produced $key$ can form a valid triplet with nums[i].

      2. Add $value$ (i.e., the frequency of $key$) to the result.

5. After processing all elements, return result as the total number of valid triplets.

Let’s look at the following illustration to get a better understanding of the solution: