Massive Algorithms: LeetCode 982 - Triples with Bitwise AND Equal To Zero

LeetCode 982 - Triples with Bitwise AND Equal To Zero

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

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

Example 1:

Input: [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

Note:

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

X.
https://github.com/cherryljr/LeetCode/blob/master/Triples%20with%20Bitwise%20AND%20Equal%20To%20Zero.java

 * 本题所给出的数据规模对于解题是相当重要的。
 * 首先，因为数组大小在 1000 级别，所以算法的时间复杂度应该在 O(n^2).
 * 因此如果采用暴力求解所有组合（O(n^3)）的方法是会超时的。
 * 其次，我们发现 A[i] 的大小不会超过 2^16 = 65536，
 * 这里给了我们一个非常重要的提示：应该利用 A[i] 的大小对状态进行压缩。
 * 因此我们可以很容易想出如下解法：
 *  1. 遍历所有的 两两相与 的数，然后记录在 Map 中
 *  key:两数相与的值; value:该数出现的次数
 *  2. 遍历 A[] 中所有的数 与 Map 中所有的 key 相与，
 *  如果结果为 0，则 res += map.get(a&b)
 * 
 * 时间复杂度：O(n^2 + n*max(A[i]))
 * 空间复杂度：O(n)
 */
    public int countTriplets(int[] A) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : A) {
            for (int b : A) {
                map.put(a & b, map.getOrDefault(a & b, 0) + 1);
            }
        }

        for (int a : A) {
            for (Map.Entry<Integer, Integer> set : map.entrySet()) {
                if ((a & set.getKey()) == 0) {
                    res += set.getValue();
                }
            }
        }
        return res;
    }

 * Approach 2: Using Array instead of HashMap
 * 因为题目明确给出了数据范围，所以这里可以使用 数组 来替代 HashMap，从而实现对代码的加速。
 * 同时，这里在第二次遍历的时候，当 (a & num) != 0 时，利用了 num += (a & num) - 1 实现加速。
 * 原理在于，因为 (a & num) != 0，所以 [num, num+(a&num)-1] 之间的数都不可能和 a 与出 0 这个结果。
 * 因此可以直接跳过这段区间。
 *
 * 时间复杂度：O(n^2 + n*max(A[i]))
 * 空间复杂度：O(1 << 16) = O(1)
 */
    public int countTriplets(int[] A) {
        // max 表示所能与出来的最大值
        int res = 0, max = -1;
        // 根据数据范围初始化 map[]
        int[] map = new int[1 << 16];
        for (int a : A) {
            for (int b : A) {
                map[a & b]++;
                max = Math.max(max, a & b);
            }
        }

        for (int a : A) {
            for (int num = 0; num <= max; num++) {
                if ((a & num) == 0) {
                    res += map[num];
                } else {
                    num += (a & num) - 1;
                }
            }
        }
        return res;
    }

https://github.com/lrscy/LeetCode/blob/master/Algorithm/982-Triples%20with%20Bitwise%20AND%20Equal%20To%20Zero.cpp

    int countTriplets(vector<int>& A) {
        int n = A.size();
        int inv[1 << 16] = { 0 };
        for( auto a : A ) {
            for( int i = 0; i < ( 1 << 16 ); ++i )
                if( ( a & i ) == 0 )
                    ++inv[i];
        }
        int ret = 0;
        for( int i = 0; i < n; ++i ) {
            for( int j = 0; j < n; ++j ) {
                ret += inv[A[i] & A[j]];
            }
        }
        return ret;
    }

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/227309/C%2B%2B-naive-O(n-*-n)

First, we process all tuples A[i] and A[j], and store the result of A[i] & A[j] in the hash map tuples. We also count there how many times each result was produced.

Then, we go through the array again, and check each element against all tuples. If it produces zero, we add the tuple counter to the result.

int countTriplets(vector<int>& A, int cnt = 0) {
  unordered_map<int, int> tuples;
  for (auto a : A)
    for (auto b : A) ++tuples[a & b];
  for (auto a : A)
    for (auto t : tuples)
      if ((t.first & a) == 0) cnt += t.second;
  return cnt;
}

Complexity Analysis

Time: O(n * n). We can have 2^16 tuples at most. When n is large, n * n will dominate n * 2^16. So it is O(n * n) in the big O notation.
Memory: O(n) for the first solution; O(2 ^ 16), or, stricter, O(1) for the second one.

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/226778/C%2B%2B-20-lines56msenumerate-with-memory-(with-Chinese-translation)

首先枚举 i 和 j，同时使用一个数组 f 记录 A[i] & A[j] 的值所对应的答案个数，即有多少个数字能使得 A[i] & A[j] & x == 0。First, we enumerate i and j, and use a vector f to save the number of solutions corresponding to A[i] & A[j], i.e. the number of x such that A[i] & A[j] & x == 0.
枚举时，如果对应的 A[i] & A[j] 还没有记录，则暴力枚举 k，求出后将其添加到 f 中。如果有记录，则不再枚举，直接使用这个记录的值。 When enumerating, if there is no record for A[i] & A[j], we will use brute force to compute the number of k, and then save it into the vector f. Otherwise, we can use this record directly.

class Solution {
public:
    int countTriplets(vector<int>& A) {
        int n = A.size(), ans = 0;
        vector<int> f(1 << 16, -1);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                int x = A[i] & A[j];
                if (f[x] == -1) {
                    f[x] = 0;
                    for (int k = 0; k < n; k++)
                        if ((x & A[k]) == 0)
                            f[x]++;
                }
                ans += f[x];
            }

        return ans;
    }

https://zxi.mytechroad.com/blog/bit/leetcode-982-triples-with-bitwise-and-equal-to-zero/
Time complexity: O(n^2 + n * max(A))
Space complexity: O(max(A)

  int countTriplets(vector<int>& A) {

    const int n = *max_element(begin(A), end(A));

    vector<int> count(n + 1);

    for (int a: A)

      for (int b: A)

        ++count[a & b];

    int ans = 0;

    for (int a : A)

      for (int i = 0; i <= n; ++i)

        if ((a & i) == 0) ans += count[i];

    return ans;

}

X. https://www.acwing.com/solution/leetcode/content/876/
类似于算法 1，我们设计状态 f(i,j)f(i,j) 表示取了 ii 个数字，其按位与的值为 jj 的方案数。
初始时，对于每个 jj，都有 f(0, A[j]) += 1。
转移时，枚举取的第 ii 个数字 A[j]A[j]，再枚举上一次按位与的值，转移 f(i, s & A[j]) += f(i - 1, s)。
最后答案为 f(2,0)f(2,0)。
时间复杂度
状态数为 O(m)O(m)，每次转移需要 O(n)O(n) 的时间，故总时间复杂度为 O(nm)O(nm)。
实际运行起来比较慢，因为所有 65536 个状态都需要遍历。
状态数位 O(m)O(m)，故空间复杂度为 O(m)O(m)。

int countTriplets(vector<int>& A) {

int n = A.size();

vector<vector<int>> f(3, vector<int>(1 << 16, 0));

for (int i = 0; i < n; i++)

f[0][A[i]]++;

for (int i = 1; i < 3; i++)

for (int s = 0; s < (1 << 16); s++)

for (int j = 0; j < n; j++)

f[i][s & A[j]] += f[i - 1][s];

return f[2][0];

}

LeetCode 982 - Triples with Bitwise AND Equal To Zero

Labels

Popular Posts