982

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] < 216

Companies:
Flipkart

Related Topics:
Array, Hash Table, Bit Manipulation

Solution 1.

Let's say a triple is a, b, c. It takes O(N^2) time to enumerate all the a, b pairs, but there will be only 2^16 numbers of a & b values. Since at worst N^2 = 1e6 and 2^16 = 65536 = 6e4, encoding the O(N^2) data into a O(2^16) data by counting different a & b values can save time.

So we first count different a & b values using O(N^2) time and O(M) = O(2^16) space, then enumerate all a & b and c pairs using O(MN) time.

// OJ: https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/
// Author: github.com/lzl124631x
// Time: O(N^2 + NM) where `N` is the length of `A`, and `M` is the range of values in `A`.
// Space: O(M)
class Solution {
public:
    int countTriplets(vector<int> &A) {
        int cnt[1 << 16] = {}, ans = 0;
        for (int a : A) {
            for (int b : A) ++cnt[a & b];
        }
        for (int n : A) {
            for (int i = 0; i < (1 << 16); ++i) {
                if ((i & n) == 0) ans += cnt[i];
            }
        }
        return ans;
    }
};