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; } };