Skip to main content

Bitwise and 3-tuples

by Kevin Nasto in AlgoSIG 3

Description

Given an array of numbers, A, find the number of 3-tuples (i, j, k) indices in A, where the bitwise AND is equal to 0. Assume the numbers in A are between 0 and 2^16.

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:

Input: arr = [1,2,3]
Output: 12

Solution

import collections


def countTriplets(A):
   """
   :type A: List[int]
   :rtype: int
   """
   cnt = collections.defaultdict(int)
   for x in A:
       for y in A:
           cnt[x & y] += 1
   res = 0
   for num in A:
       for key in cnt.keys():
           if num & key == 0:
               res += cnt[key]
   return res

Comments

Comments powered by Disqus