Problem Description

You are given an integer array nums. Your task is to count the number of triplets (i, j, k) such that:

• 0 ≤ i, j, k < nums.length
• The bitwise AND of nums[i], nums[j], and nums[k] is equal to 0 (i.e., nums[i] & nums[j] & nums[k] == 0).
• Elements can be reused; that is, i, j, and k can be equal or different.

Thought Process

At first glance, the problem seems to require checking all possible triplets in the array. For each combination of i, j, and k, we would compute nums[i] & nums[j] & nums[k] and see if the result is zero.

However, with up to 1000 elements, there are up to 1,000,000,000 (10⁹) possible triplets, which is far too many for a brute-force approach.

We need to find a way to avoid checking every triplet individually. This leads us to consider whether we can count the number of valid pairs or partial results in advance, and use that to speed up the solution.

The key insight is that the bitwise AND operation is associative and commutative, and the constraints on the numbers are small (16 bits), so we can use this to precompute and optimize.

Solution Approach

We'll break down the optimized algorithm step by step:

1. Precompute all pairwise ANDs:
   • For all pairs (a, b) in nums, compute nums[a] & nums[b].
   • Count how many times each result occurs using a hash map or array (since possible AND results are at most 2¹⁶).
2. Count valid triplets:
   • For each number c in nums, and for each possible value x (the result of nums[a] & nums[b]), if (x & c) == 0, then all pairs (a, b) with AND x can form a valid triplet with c.
   • Sum up the counts for all such x and c combinations.
3. Why this works:
   • Because the constraints are small, the number of unique AND results is limited (at most 65536), making it feasible to precompute and iterate over them.
   • This reduces the time complexity from O(n³) to O(n² + n × 65536).

Example Walkthrough

Let's walk through an example with nums = [2, 1, 3].

Step 1: Compute all pairwise ANDs

• 2 & 2 = 2
• 2 & 1 = 0
• 2 & 3 = 2
• 1 & 2 = 0
• 1 & 1 = 1
• 1 & 3 = 1
• 3 & 2 = 2
• 3 & 1 = 1
• 3 & 3 = 3

• 0: 2 times
• 1: 3 times
• 2: 3 times
• 3: 1 time

• For c = 2: Which AND results can form 0 with 2?
• Check 0 & 2 = 0 (yes), 1 & 2 = 0 (yes), 2 & 2 = 2 (no), 3 & 2 = 2 (no).
• So, for c = 2, valid counts are those for 0 and 1: 2 + 3 = 5
• Repeat for c = 1 and c = 3 similarly:
• For c = 1: 0 & 1 = 0 (yes), 1 & 1 = 1 (no), 2 & 1 = 0 (yes), 3 & 1 = 1 (no).
• So, valid counts for c = 1 are for 0 and 2: 2 + 3 = 5
• For c = 3: 0 & 3 = 0 (yes), 1 & 3 = 1 (yes), 2 & 3 = 2 (yes), 3 & 3 = 3 (no).
• So, valid counts for c = 3 are for 0, 1, 2: 2 + 3 + 3 = 8

Time and Space Complexity

Brute-force approach:

• Time complexity: O(n³) because you check every possible triplet.
• Space complexity: O(1) extra space.

• Time complexity: O(n² + n × 65536), which is efficient for the given constraints. The first part is for precomputing all pairs, and the second is for checking all possible AND results against each number.
• Space complexity: O(65536) to store the counts of all possible AND results.

Code Implementation

from collections import Counter

class Solution:
    def countTriplets(self, nums):
        pair_count = Counter()
        for a in nums:
            for b in nums:
                pair_count[a & b] += 1

        result = 0
        for c in nums:
            for x in pair_count:
                if (x & c) == 0:
                    result += pair_count[x]
        return result
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        unordered_map<int, int> pair_count;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                pair_count[nums[i] & nums[j]]++;
            }
        }
        int result = 0;
        for (int k = 0; k < n; ++k) {
            for (auto& [x, cnt] : pair_count) {
                if ((x & nums[k]) == 0) {
                    result += cnt;
                }
            }
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int countTriplets(int[] nums) {
        Map<Integer, Integer> pairCount = new HashMap<>();
        int n = nums.length;
        for (int a : nums) {
            for (int b : nums) {
                int x = a & b;
                pairCount.put(x, pairCount.getOrDefault(x, 0) + 1);
            }
        }
        int result = 0;
        for (int c : nums) {
            for (Map.Entry<Integer, Integer> entry : pairCount.entrySet()) {
                if ((entry.getKey() & c) == 0) {
                    result += entry.getValue();
                }
            }
        }
        return result;
    }
}
      

var countTriplets = function(nums) {
    const pairCount = new Map();
    for (let a of nums) {
        for (let b of nums) {
            const x = a & b;
            pairCount.set(x, (pairCount.get(x) || 0) + 1);
        }
    }
    let result = 0;
    for (let c of nums) {
        for (let [x, cnt] of pairCount.entries()) {
            if ((x & c) === 0) {
                result += cnt;
            }
        }
    }
    return result;
};
      

Summary

The key to efficiently solving this problem is leveraging the limited number of possible bitwise AND results due to the 16-bit constraint. By precomputing all possible pairwise ANDs and counting them, we can quickly determine for each number how many pairs it can form a valid triplet with. This turns a cubic-time brute-force problem into a much faster solution, making it feasible for large input sizes and demonstrating the power of precomputation and bit manipulation.