Triples with Bitwise AND Equal To Zero — DSA

Problem#

Count triplets (i, j, k) of indices into nums (with repetition allowed and order mattering) such that nums[i] & nums[j] & nums[k] == 0.

Examples#

[2,1,3] → 12.
[0,0,0] → 27.

Constraints#

1 <= nums.length <= 1000, 0 <= nums[i] < 2^16.

Approach#

Precompute pairAnd[v] = number of ordered (i, j) with nums[i] & nums[j] == v. Then for each k, sum pairAnd[v] over all v with v & nums[k] == 0. Enumerating those v cleverly uses the submask trick: iterate all submasks of ~nums[k] capped to 16 bits.

Solution#

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        const int N = 1 << 16;
        vector<int> pairAnd(N, 0);
        for (int a : nums)
            for (int b : nums)
                ++pairAnd[a & b];
        int ans = 0;
        for (int c : nums) {
            int comp = (~c) & (N - 1);
            for (int sub = comp; ; sub = (sub - 1) & comp) {
                ans += pairAnd[sub];
                if (sub == 0) break;
            }
        }
        return ans;
    }
};

func countTriplets(nums []int) int {
  const N = 1 << 16
  pairAnd := make([]int, N)
  for _, a := range nums {
    for _, b := range nums {
      pairAnd[a&b]++
    }
  }
  ans := 0
  for _, c := range nums {
    comp := (^c) & (N - 1)
    for sub := comp; ; sub = (sub - 1) & comp {
      ans += pairAnd[sub]
      if sub == 0 {
        break
      }
    }
  }
  return ans
}

from typing import List

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        N = 1 << 16
        pair_and = [0] * N
        for a in nums:
            for b in nums:
                pair_and[a & b] += 1
        ans = 0
        for c in nums:
            comp = (~c) & (N - 1)
            sub = comp
            while True:
                ans += pair_and[sub]
                if sub == 0:
                    break
                sub = (sub - 1) & comp
        return ans

var countTriplets = function(nums) {
    const N = 1 << 16;
    const pairAnd = new Int32Array(N);
    for (const a of nums) {
        for (const b of nums) {
            pairAnd[a & b]++;
        }
    }
    let ans = 0;
    for (const c of nums) {
        const comp = (~c) & (N - 1);
        let sub = comp;
        while (true) {
            ans += pairAnd[sub];
            if (sub === 0) break;
            sub = (sub - 1) & comp;
        }
    }
    return ans;
};

class Solution {
    public int countTriplets(int[] nums) {
        final int N = 1 << 16;
        int[] pairAnd = new int[N];
        for (int a : nums) {
            for (int b : nums) {
                pairAnd[a & b]++;
            }
        }
        int ans = 0;
        for (int c : nums) {
            int comp = (~c) & (N - 1);
            int sub = comp;
            while (true) {
                ans += pairAnd[sub];
                if (sub == 0) break;
                sub = (sub - 1) & comp;
            }
        }
        return ans;
    }
}

function countTriplets(nums: number[]): number {
    const N: number = 1 << 16;
    const pairAnd: Int32Array = new Int32Array(N);
    for (const a of nums) {
        for (const b of nums) {
            pairAnd[a & b]++;
        }
    }
    let ans: number = 0;
    for (const c of nums) {
        const comp: number = (~c) & (N - 1);
        let sub: number = comp;
        while (true) {
            ans += pairAnd[sub];
            if (sub === 0) break;
            sub = (sub - 1) & comp;
        }
    }
    return ans;
}

Editorial#

(a & b & c) == 0 is equivalent to (a & b) being a submask of ~c. Building the AND distribution of pairs is O(n^2). Iterating submasks of ~c for each c totals at most O(n * 3^16) in theory but is far less in practice because most masks are small.

Complexity#

Time: ~O(n^2 + n * 2^16).
Space: O(2^16).

Concept revision#

Subsets

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#