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.length0 <= j < A.length0 <= k < A.lengthA[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 <= 10000 <= 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;
}
}