982. Triples with Bitwise AND Equal To Zero
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int countTriplets(vector<int>& A) {
unordered_map<int ,int> freq;
int res = 0, n = A.size(), z = 0;
for(int i = 0; i < n; i++) {
if(A[i] == 0) z += 1;
for(auto [k,v] : freq) {
if(k & A[i]) continue;
res += v;
}
for(int j = 0; j < i; j++) {
freq[A[i] & A[j]]++;
}
freq[A[i]]++;
}
return res * 6 + z;
}
};
|
