Triples with Bitwise AND Equal To Zero

hard bit manipulation hash map bitmask

Problem

Given an integer array nums, return the number of ordered triples of indices (i, j, k) such that nums[i] & nums[j] & nums[k] == 0, where & is the bitwise AND operator. Indices may repeat.

Inputnums = [2, 1, 3]

Output12

For every ordered pair we precompute its AND; pairing 2 & 1 = 0 and other combinations yields 12 valid triples in total.

nums (comma-separated, small non-negative ints)

def count_triplets(nums):
    pair = {}
    for a in nums:
        for b in nums:
            pair[a & b] = pair.get(a & b, 0) + 1
    total = 0
    for c in nums:
        for p, cnt in pair.items():
            if p & c == 0:
                total += cnt
    return total

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

class Solution {
    public int countTriplets(int[] nums) {
        Map<Integer, Integer> pair = new HashMap<>();
        for (int a : nums)
            for (int b : nums)
                pair.merge(a & b, 1, Integer::sum);
        int total = 0;
        for (int c : nums)
            for (Map.Entry<Integer, Integer> e : pair.entrySet())
                if ((e.getKey() & c) == 0) total += e.getValue();
        return total;
    }
}

int countTriplets(vector<int>& nums) {
    unordered_map<int, int> pair;
    for (int a : nums)
        for (int b : nums)
            pair[a & b]++;
    int total = 0;
    for (int c : nums)
        for (auto& e : pair)
            if ((e.first & c) == 0) total += e.second;
    return total;
}

Explanation

We count ordered triples (i, j, k) where nums[i] & nums[j] & nums[k] == 0. Trying all triples would be O(n^3), so we precompute the pairs and reuse them.

First we build a frequency map pair over all ordered pairs: for every a and b in nums, we record their AND result a & b and how many pairs produce it. This collapses the first two indices into a table of O(n^2) AND-values.

Then for each third value c, we scan the map and add cnt for every stored result p where p & c == 0. Each such match means a pair whose AND, further ANDed with c, gives zero — a valid triple.

Because AND results are bounded by the value range (the keys K are limited), the second phase is O(n * K) rather than another O(n^2) pass, which is the whole speedup.

Example: nums = [2, 1, 3]. Building the pair-AND table and then matching each c against entries that AND to zero gives 12 ordered triples.

Time: O(n² + n·K) Space: O(K)