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

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: class Solution:
    def countTriplets(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def countTriplets(self, A: List[int]) -> int:
		counters = [0] * (1 << 16)
		counters[0] = len(A)
		for num in A:
			mask = ~num & (1 << 16) - 1
			sm = mask
			while sm != 0:
				counters[sm] += 1
				sm = sm - 1 & mask
		return sum((counters[num1 & num2] for num1 in A for num2 in A))


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = defaultdict(int)
		for a in A:
			for b in A:
				d[a & b] += 1
		return sum((d[ab] for c in A for ab in d if not ab & c))


from collections import Counter

class Solution(object):

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


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		and_values = {}
		for x in A:
			for y in A:
				c = x & y
				if c in and_values:
					and_values[c] += 1
				else:
					and_values[c] = 1
		triplet_count = 0
		for a in and_values:
			for z in A:
				if a & z == 0:
					triplet_count += and_values[a]
		return triplet_count


from collections import Counter
from functools import lru_cache
from itertools import product

class Solution:

	def countTriplets(self, A: List[int]) -> int:

		@lru_cache(None)
		def count_and_zero(x):
			return sum((1 for a in A if a & x == 0))
		pair_and_count = Counter((x & y for (x, y) in product(A, A)))
		return sum((count_and_zero(x) * cnt for (x, cnt) in list(pair_and_count.items())))


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		memo = {}
		for i in A:
			for j in A:
				memo[i & j] = memo.get(i & j, 0) + 1
		res = 0
		for num in A:
			for k in memo:
				if num & k == 0:
					res += memo[k]
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		t = 0
		d = {}
		for i in A:
			for j in A:
				a = i & j
				if a in d:
					d[a] += 1
				else:
					d[a] = 1
		for k in d:
			for i in A:
				if k & i == 0:
					t += d[k]
		return t


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		count = collections.defaultdict(int)
		ret = 0
		for i in A:
			for j in A:
				count[i & j] += 1
		for i in A:
			for j in count:
				if i & j == 0:
					ret += count[j]
		return ret


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		count = 0
		dic = collections.defaultdict(int)
		for i in range(n):
			for j in range(n):
				dic[A[i] & A[j]] += 1
		ans = 0
		for ele in A:
			for res in dic:
				if res & ele == 0:
					ans += dic[res]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		c = Counter((x & y for x in A for y in A))
		return sum([c[xy] for xy in c for z in A if xy & z == 0])


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = defaultdict(int)
		mask = (1 << 16) - 1
		for i in A:
			high = mask ^ i
			j = high
			while j:
				d[j] += 1
				j = j - 1 & high
			d[0] += 1
		res = 0
		for i in A:
			for j in A:
				res += d[i & j]
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		l = len(A)
		Memo = {}
		for i in range(l):
			for j in range(i + 1):
				t = A[i] & A[j]
				if t not in Memo:
					Memo[t] = 0
				if i == j:
					Memo[t] += 1
				else:
					Memo[t] += 2
		r = 0
		for a in A:
			for key in Memo:
				if key & a == 0:
					r += Memo[key]
		return r


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = {}
		for i in A:
			for j in A:
				if i & j in d:
					d[i & j] += 1
				else:
					d[i & j] = 1
		c = 0
		for i in A:
			for j in d:
				if i & j == 0:
					c += d[j]
		return c


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		tmp = {}
		for a in A:
			for b in A:
				if a & b in tmp:
					tmp[a & b] += 1
				else:
					tmp[a & b] = 1
		ans = 0
		for (k, t) in tmp.items():
			for c in A:
				if c & k == 0:
					ans += t
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		mp = {}
		for i in A:
			for j in A:
				k = i & j
				mp[k] = mp.get(k, 0) + 1
		result = 0
		for i in A:
			for j in mp:
				if i & j == 0:
					result += mp[j]
		return result


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		counter = Counter()
		for a in A:
			for b in A:
				counter[a & b] += 1
		res = 0
		for a in A:
			for b in counter:
				if a & b == 0:
					res += counter[b]
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		dic = defaultdict(int)
		res = 0
		for i in A:
			for j in A:
				tmp = i & j
				dic[tmp] += 1
		for i in A:
			for j in dic:
				if i & j == 0:
					res += dic[j]
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		cnt = collections.defaultdict(int)
		for i in A:
			for j in A:
				cnt[i & j] += 1
		res = 0
		for i in A:
			for j in cnt:
				if i & j == 0:
					res += cnt[j]
		return res


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		counts = defaultdict(int)
		for x in A:
			for y in A:
				counts[x & y] += 1

		def dfs(z, xy, k):
			if k == -1:
				return counts[xy]
			answer = dfs(z, xy << 1, k - 1)
			if z >> k & 1 == 0:
				answer += dfs(z, xy << 1 | 1, k - 1)
			return answer
		answer = 0
		for z in A:
			answer += dfs(z, 0, 16)
		return answer


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		B = [bin(a)[2:] for a in A]
		(M, N) = (len(B), max(list(map(len, B))))
		B = [b.zfill(N) for b in B]
		dic = collections.defaultdict(set)
		for i in range(M):
			for j in range(N):
				if B[i][j] == '1':
					dic[j].add(i)
		Venn = collections.defaultdict(list)
		cnt = 0
		for j in range(N):
			if len(dic[j]):
				cnt += len(dic[j]) ** 3
				for i in range(j, 0, -1):
					for prv in Venn[i]:
						intersec = prv & dic[j]
						if len(intersec):
							cnt += (-1) ** i * len(intersec) ** 3
							Venn[i + 1].append(intersec)
				Venn[1].append(dic[j])
		return M ** 3 - cnt


class Solution:

	def countTriplets(self, nums):
		count_map = collections.Counter((i & j for i in nums for j in nums))
		return sum((count_map[key] for num in nums for key in count_map if num & key == 0))


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		dp = collections.defaultdict(int)
		for n1 in A:
			for n2 in A:
				dp[n1 & n2] += 1
		res = 0
		for n in A:
			for (k, v) in dp.items():
				if not k & n:
					res += v
		return res


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		pairs = defaultdict(int)
		for a in A:
			for b in A:
				pairs[a & b] += 1
		res = 0
		for a in A:
			for (p, cnt) in pairs.items():
				if not a & p:
					res += cnt
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		two_and_count = collections.Counter()
		res = 0
		for (idx, x) in enumerate(A):
			if x == 0:
				res += 1
			new_two_and = collections.Counter([x])
			for idy in range(idx):
				if x & A[idy] == 0:
					res += 3
				new_two_and[A[idy] & x] += 2
			for (v, c) in two_and_count.items():
				if x & v == 0:
					res += 3 * c
			two_and_count += new_two_and
		return res

	def countTriplets_II(self, A: List[int]) -> int:
		M = 3
		N = 1 << 16
		dp = [[0] * N for _ in range(M + 1)]
		dp[0][N - 1] = 1
		for m in range(1, M + 1):
			for v in range(N):
				for a in A:
					dp[m][v & a] += dp[m - 1][v]
		return dp[M][0]


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		counter = collections.Counter()
		for i in A:
			for j in A:
				counter[i & j] += 1
		result = 0
		for k in A:
			for v in counter:
				if k & v == 0:
					result += counter[v]
		return result


import numpy as np

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		memo = dict()
		for i in range(len(A)):
			for j in range(i, len(A)):
				r = A[i] & A[j]
				memo[r] = memo.get(r, 0) + (1 if i == j else 2)
		ret = 0
		for i in range(len(A)):
			for k in memo:
				if A[i] & k == 0:
					ret += memo[k]
		return ret


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = {}
		res = 0
		for a in A:
			for b in A:
				t = a & b
				if t in d:
					d[t] += 1
				else:
					d[t] = 1
		for a in A:
			for (k, v) in list(d.items()):
				if a & k == 0:
					res += v
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		cnt = collections.Counter()
		A = list(collections.Counter(A).items())
		result = 0
		for (i, k1) in A:
			for (j, k2) in A:
				cnt[i & j] += k1 * k2
		cnt = list(cnt.items())
		for (i, k1) in A:
			if i == 0:
				result += k1 * n * n
				continue
			for (j, k2) in cnt:
				if i & j == 0:
					result += k1 * k2
		return result


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		N = len(A)
		ans = 0
		count = collections.Counter()
		for i in range(N):
			for j in range(N):
				count[A[i] & A[j]] += 1
		for k in range(N):
			for v in count:
				if A[k] & v == 0:
					ans += count[v]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		umap = collections.Counter(A)
		n = len(A)
		mask = (1 << 16) - 1
		for i in range(n):
			for j in range(i + 1, n):
				key = A[i] & A[j]
				if key not in umap:
					umap[key] = 0
				umap[key] += 2
		result = 0
		for a in A:
			d = ~a & mask
			key = d
			result += umap.get(d, 0)
			while d > 0:
				d = d - 1 & key
				result += umap.get(d, 0)
		return result


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		cnt = collections.Counter()
		result = 0
		for i in A:
			for j in A:
				cnt[i & j] += 1
		for i in A:
			for (j, k) in cnt.items():
				if i & j == 0:
					result += k
		return result


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		cnt = 0
		d = {}
		for i in range(len(A)):
			for j in range(len(A)):
				if A[i] & A[j] not in d:
					d[A[i] & A[j]] = 1
				else:
					d[A[i] & A[j]] += 1
		for i in range(len(A)):
			for j in d:
				if A[i] & j == 0:
					cnt += d[j]
		return cnt


from collections import defaultdict
from collections import Counter

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		combo = collections.Counter((x & y for x in A for y in A))
		res = 0
		for a in A:
			for (k, v) in list(combo.items()):
				if a & k == 0:
					res += v
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		combo = collections.Counter((x & y for x in A for y in A))
		return sum((combo[k] for z in A for k in combo if z & k == 0))


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		ans = 0
		A_counts = defaultdict(lambda : 0)
		for num in A:
			A_counts[num] += 1
		counts = defaultdict(lambda : 0)
		for (n1, count1) in list(A_counts.items()):
			for (n2, count2) in list(A_counts.items()):
				counts[n1 & n2] += count1 * count2
		for (n1, count1) in list(A_counts.items()):
			for (n2, count2) in list(counts.items()):
				if n1 & n2 == 0:
					ans += count1 * count2
		return ans


from collections import Counter

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		cnt = Counter()
		for a in A:
			for b in A:
				cnt[a & b] += 1
		res = 0
		for a in A:
			for (k, v) in cnt.items():
				if a & k == 0:
					res += v
		return res


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		count = 0
		dic = dict()
		for i in range(len(A)):
			for j in range(i, len(A)):
				r = A[i] & A[j]
				dic[r] = dic.get(r, 0) + (1 if i == j else 2)
		result = 0
		for i in range(len(A)):
			for k in dic:
				if A[i] & k == 0:
					result += dic[k]
		return result


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		N = len(A)
		ans = 0
		count = dict()
		for i in range(N):
			for j in range(N):
				tmp = A[i] & A[j]
				if tmp not in count:
					count[tmp] = 1
				else:
					count[tmp] += 1
		for k in range(N):
			for v in count:
				if A[k] & v == 0:
					ans += count[v]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = {}
		ans = 0
		for i in range(len(A)):
			for j in range(len(A)):
				a = A[i] & A[j]
				d[a] = d.get(a, 0) + 1
		for i in range(len(A)):
			for j in list(d.keys()):
				if A[i] & j == 0:
					ans += d[j]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		C = defaultdict(int)
		for i in range(n):
			C[A[i]] += 1
			for j in range(i + 1, n):
				C[A[i] & A[j]] += 2
		return sum((c * sum((x & y == 0 for y in A)) for (x, c) in C.items()))


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		n2 = n * n
		dp = {}
		ways = 0
		for i in range(n):
			for j in range(n):
				res = A[i] & A[j]
				dp[res] = dp.get(res, 0) + 1
		for i in range(n):
			for (tgt, ct) in dp.items():
				if A[i] & tgt == 0:
					ways += ct
		return ways


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)
		ans = 0
		counts = defaultdict(lambda : 0)
		for i in range(n):
			for j in range(n):
				counts[A[i] & A[j]] += 1
		for k in range(n):
			for (num, count) in list(counts.items()):
				if num & A[k] == 0:
					ans += count
		return ans


from collections import defaultdict

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		mp = defaultdict(int)
		mask = (1 << 16) - 1
		for x in A:
			y = mask ^ x
			s = y
			while s:
				mp[s] += 1
				s = s - 1 & y
		n = len(A)
		cnt = 0
		for i in range(n):
			if A[i] == 0:
				cnt += n * n
				continue
			for j in range(n):
				if A[i] & A[j] == 0:
					cnt += n
					continue
				cnt += mp[A[i] & A[j]]
		return cnt


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		from collections import defaultdict
		dic = defaultdict(int)
		n = len(A)
		dp = defaultdict(int)
		for i in range(n):
			for j in range(n):
				dic[i, j] = A[i] & A[j]
				dp[A[i] & A[j]] += 1
		ans = 0
		for i in range(n):
			for x in dp:
				if x & A[i] == 0:
					ans += dp[x]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		d = dict()
		for i in range(len(A)):
			for j in range(len(A)):
				product = A[i] & A[j]
				if product in d:
					d[product] += 1
				else:
					d[product] = 1
		ans = 0
		for i in range(len(A)):
			for (k, v) in d.items():
				if A[i] & k == 0:
					ans += v
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		n = len(A)

		@lru_cache(None)
		def dfs(i, pre):
			if i == 4 and (not pre):
				return 1
			ans = 0
			for a in A:
				if i > 1 and (not pre & a) or (i == 1 and (not a)):
					ans += n ** (3 - i)
				elif i < 3:
					ans += dfs(i + 1, pre & a if i > 1 else a)
			return ans
		return dfs(1, None)


from collections import Counter

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		c = Counter()
		for val in A:
			val = ~val & 65535
			mask = val
			c[val] += 1
			while val > 0:
				val = val - 1 & mask
				c[val] += 1
		ans = 0
		for v1 in A:
			for v2 in A:
				val = v1 & v2
				if val in c:
					ans += c[val]
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		tot = 1 << 16
		cnt = [0 for _ in range(tot)]
		for a in A:
			for b in A:
				cnt[a & b] += 1
		ans = 0
		for e in A:
			s = 0
			while s < tot:
				if s & e == 0:
					ans += cnt[s]
					s += 1
				else:
					s += e & s
		return ans


class TrieNode:

	def __init__(self):
		self.children = [None] * 2
		self.count = 0
		self.cache = {}

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, num):
		now = self.root
		for j in range(16):
			i = num & 1
			if not now.children[i]:
				now.children[i] = TrieNode()
			now = now.children[i]
			num >>= 1
		now.count += 1

	def match(self, num):
		return self.count_match(self.root, num)

	def count_match(self, now, num):
		if not now:
			return 0
		if num in now.cache:
			return now.cache[num]
		if now.count > 0:
			return now.count
		bit = num & 1
		next_num = num >> 1
		if bit:
			now.cache[num] = self.count_match(now.children[0], next_num)
		else:
			tmp = 0
			tmp += self.count_match(now.children[0], next_num)
			tmp += self.count_match(now.children[1], next_num)
			now.cache[num] = tmp
		return now.cache[num]

class Solution:

	def countTriplets(self, A: List[int]) -> int:
		trie = Trie()
		for num in A:
			trie.insert(num)
		cache = {}
		ans = 0
		for num1 in A:
			for num2 in A:
				num = num1 & num2
				a = trie.match(num)
				ans += a
		return ans