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

# 982. Triples with Bitwise AND Equal To Zero

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. 1 <= A.length <= 1000
2. 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;
}
};