# 982. 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. `1 <= A.length <= 1000`
2. `0 <= A[i] < 2^16`

``````class Solution {
public:
int countTriplets(vector<int>& A) {
int res = 0;
unordered_map<int, int> m;
for (int a : A) {
for (int b : A) {
++m[a & b];
}
}
for (int num : A) {
for (auto a : m) {
if ((num & a.first) == 0) {
res += a.second;
}
}
}
return res;
}
};
``````

``````class Solution {
public:
int countTriplets(vector<int>& A) {
int res = 0;
vector<int> cnt(1 << 16, -1);
for (int a : A) {
for (int b : A) {
int x = a & b;
if (cnt[x] == -1) {
cnt[x] = 0;
for (int num : A) {
if ((x & num) == 0) ++cnt[x];
}
}
res += cnt[x];
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/982

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

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

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/226721/Java-DP-O(3-*-216-*-n)-time-O(216)-space

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

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation