# 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
import collections


class Solution(object):
    def countTriplets(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        cnt = 0
        for i in xrange(len(A)):
            for j in xrange(i, len(A)):
                for k in xrange(j, len(A)):
                    if not A[i] & A[j] & A[k]:
                        if i == j and j == k:
                            cnt += 1
                        elif i == j or j == k:
                            cnt += 3
                        else:
                            cnt += 6
        return cnt

    def countTriplets2(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        cnt, res = collections.defaultdict(int), 0
        for i in A:
            for j in A:
                cnt[i & j] += 1

        for k in A:
            for l in cnt.keys():
                if not k & l:
                    res += cnt[l]

        return res


if __name__ == '__main__':
    print Solution().countTriplets([1, 2, 3])
    print Solution().countTriplets2([1, 2, 3])
