Description Link to heading

982. Triples with Bitwise AND Equal To Zero (Hard)

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

  • 0 <= i < nums.length
  • 0 <= j < nums.length
  • 0 <= k < nums.length
  • nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: nums = [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Example 2:

Input: nums = [0,0,0]
Output: 27

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 2¹⁶

Solution Link to heading

You can first use the hash table ump to store the result of nums[i] & nums[j], then with nums[k] by bit, if the result is 0, res += ump[nums[i] & nums[j]].

Optimization, we view binary as a set, and the ith bit in binary from low to high is 1 to indicate that i is in the set and 0 to indicate that i is not in the set, e.g. $a = 1101_{(2)}$ means that the set $A={0,2,3}$.

Then, $a & b = 0$ i.e., the set $A$ and the set $B$ do not intersect, or $B$ is the set $\complement_U A$, where $U={0,1,2,… ,15}$, the corresponding number i.e. $0xffff$, and a number isomorphic to $0xffff$ gives the complement of this number.

So, the code can be optimized to enumerate the subsets of $m = nums[k]\oplus 0xffff$.

(b) To enumerate the subset $s$ of $m$, one can keep subtracting $s$ from $m$ all the way to 0. If $s & m = s$, it means that $s$ is a subset of $m$.

A more efficient approach is to “jump” directly to the next subset, i.e., $s$ is updated to $(s - 1)& m$. The correctness of this is that $s-1$ only changes the lowest $1$ of $s$ to $0$ (consider the set corresponding to $s$), and all $0$ lower than this $1$ become $1$, so the next subset, which must be a subset of $s-1$, is obtained by directly $&m$.

Finally, when $s=0$, since the binary of $-1$ is all $1$, all $(s-1)&m = m$, so we can determine whether the next subset is back to $m$ to determine whether to exit the loop.

Note: This technique is often used in subset state compression DP

Code Link to heading 

class Solution {
public:
    int countTriplets(vector<int> &nums) {
        int cnt[1 << 16]{};
        for (int x : nums)
            for (int y : nums)
                ++cnt[x & y];
        int ans = 0;
        for (int m : nums) {
            m ^= 0xffff;
            int s = m;
            do { // including null->0
                ans += cnt[s];
                s = (s - 1) & m;
            } while (s != m);
        }
        return ans;
    }
};