Formatted question description: https://leetcode.ca/all/982.html

982. Triples with Bitwise AND Equal To Zero

Level

Hard

Description

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

Solution

Use the idea of hash map, where the counts of each bitwise AND are stored. Since the numbers are in the range [0, 2^16) after bitwise AND operation, an array can be used instead of a hash map. The array map has length 2^16.

Loop over A. For each index pair (i, j) (where i and j can be in any order and it is possible that i == j), increase map[A[i] & A[j]] by 1. Then for each i from 0 to 2^16 - 1, if map[i] > 0, loop over A and for each j such that A[j] & i is 0, increase the number of triples by map[i].

Finally, return the number of triples.

class Solution {
    public int countTriplets(int[] A) {
        int tripletsCount = 0;
        int mapLength = 1 << 16;
        int[] map = new int[mapLength];
        int length = A.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                map[A[i] & A[j]]++;
        }
        for (int i = 0; i < mapLength; i++) {
            if (map[i] != 0) {
                for (int j = 0; j < length; j++) {
                    if ((A[j] & i) == 0)
                        tripletsCount += map[i];
                }
            }
        }
        return tripletsCount;
    }
}

```
Todo
```

class Solution {
public:
    int countTriplets(vector<int>& A) {
        const int N = A.size();
        int res = 0;
        unordered_map<int, int> m_;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                ++m_[(A[i] & A[j])];
            }
        }
        for (int i = 0; i < N; ++i) {
            for (auto a : m_) {
                if ((A[i] & a.first) == 0)
                    res += a.second;
            }
        }
        return res;
    }
};

982 - Triples with Bitwise AND Equal To Zero

982. Triples with Bitwise AND Equal To Zero

Level

Description

Solution

All Problems

All Solutions