Algorithm
Problem Name: 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.length0 <= j < nums.length0 <= k < nums.lengthnums[i] & nums[j] & nums[k] == 0, where&represents the bitwise-AND operator.
Example 1:
Input: nums = [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
Example 2:
Input: nums = [0,0,0] Output: 27
Constraints:
1 <= nums.length <= 10000 <= nums[i] < 216
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const countTriplets = function (A) {
const N = 1 << 16,
M = 3
const dp = Array.from({ length: M + 1 }, () => Array(N).fill(0))
dp[0][N - 1] = 1
for (let i = 0; i < M; i++) {
for (let k = 0; k < N; k++) {
for (let a of A) {
dp[i + 1][k & a] += dp[i][k]
}
}
}
return dp[M][0]
}
Input
nums = [2,1,3]
Output
12
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countTriplets(self, A: List[int]) -> int:
cnt = collections.Counter([a & b for a in A for b in A])
return sum(cnt[k] for a in A for k in cnt if not a & k)
Input
nums = [2,1,3]
Output
12