Problem statement

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

Solution 1

Let us use the fact than numbers are not very big, that is < 2^16. So, we can evaluate AND of all pairs in O(n^2). Then we can again evaluate pairs in O(n * 2^16).

Complexity

Time complexity is O(n * 2^16).

Code

class Solution:
    def countTriplets(self, A):
        B = Counter(x&y for x, y in product(A, A))
        return sum(B[xy] for z, xy in product(A, B) if xy & z == 0)

Solution 2

For each element A[i] evaluate complementary mask, i.e for 1010010, mask is 0101101, then we traverse all submasks and and update dp. Then for each pair i & j from A we check how many values we have.

Complexity

It is also O(n * 2^16), but it works several times faster.

Code

class Solution:
    def countTriplets(self, A):
        n = len(A)
        dp = [0] * (1 << 16)
        for i in range(n):
            state = A[i] ^ ((1 << 16) - 1)
            sub = state
            while sub:
                dp[sub] += 1
                sub = state & (sub - 1)
            dp[0] += 1

        return sum(dp[i & j] for i, j in product(A, A))