Efficient way to count the number of ways to select 3 numbers from a given list has their AND(bit-wise) equal 0

algorithmscombinationscombinatoricscomputational complexity

Suppose a list A contains non-negative numbers no larger than $2^8$.

Eg. A = {4, 9, 6, 1, 15, 8, 3, 5, 18, 7}

I want to find the number of selecting 3 members of A such that their AND bit-wise equals 0.

An example of 3 members of A has AND bit-wise equal to 0 would be{4, 6, 9}

Binary of 4 = 0100

Binary of 6 = 0110

Binary of 9 = 1001

Therefore 4 & 6 & 9 = 0

For the example above, using exhaustive search, there are 82 ways. By exhaustive search, I use 3 loops, therefore running time would be $O(n^3)$
Example of brute-force approach in Python:

counts = 0
A = [4, 9, 6, 1, 15, 8, 3, 5, 18, 7]

for i in range(0, len(A)):
    for j in range(i + 1, len(A)):
        for k in range(j + 1, len(A)):
            if A[i] & A[j] & A[k] == 0:
                counts += 1

print(counts) # return 82

I want to know that if it is possible to do better than exhaustive search – $O(n^3)$? If the conditions is changed to find 3 members sum up to certain value, we can use hash function to store and run 2 loops instead to improve the bound but I don't see the same approach works for AND bit-wise.

Edit: Noble Mushtak pointed out that keeping separate bits in different hash tables, I can achieve running time $O(n^2)$. Now, I wonder, is this the best bound possible for this problem?

Best Answer

Just like addition, AND is an associative operation, so I don't understand your argument against hash-tables for this problem. Using a table worked fine for me:

A = [4, 9, 6, 1, 15, 8, 3, 5, 18, 7]
counts = 0
# Here, i is the index of the middle number in the triplet we are going to pick
for i in range(len(A)):
    # storage[l] represents the number of pairs such that:
    # A[j] & A[i] == l for some j < i
    # Thus, j is the index of the first number in the triplet we are going to pick
    storage = [0]*(1 << 8)
    for j in range(i):
        storage[A[j] & A[i]] += 1
    # Finally, k is the index of the last number in the triplet
    for k in range(i+1, len(A)):
        # If l & A[k] is 0, then we found some pairs for which
        # A[j] & A[i] & A[k] == 0 holds true,
        # so add the number of pairs (i.e. storage[l]) to counts.
        for l in range(len(storage)):
            if l & A[k] == 0: counts += storage[l]
print(counts) # Outputs 82

Here, the complexity is $O(n^2 2^b)$, where $b$ is the number of bits, but since $b=8$, I don't think the $2^b$ is really that much of an issue.

Also, we can reduce the complexity even further to $O(n^2+n2^b)$ by using a two-dimensional table.

import copy

A = [4, 9, 6, 1, 15, 8, 3, 5, 18, 7]
counts = 0
# storage[i][l] represents the number of pairs A[j] & A[j2] == l
# where j2 <= i
storage = [[0]*(1 << 8)]
# Again, i and j are the indexes of
# the middle and first numbers, respectively, of the triplet
for i in range(len(A)-1):
    # Add all the pairs of A[j] & A[i] to storage[i]:
    for j in range(i):
        storage[i][A[j] & A[i]] += 1
    # Then, add all of the pairs from storage[i] to storage[i+1]
    # since storage[i] is supposed to be a cumulative array of
    # all the pairs of ANDs from before and up until the index i
    storage.append(copy.deepcopy(storage[-1]))
# Again, k is the index of the last element in the triplet
for k in range(1, len(A)):
    # If l & A[k] is 0, then add all of the pairs before k
    # (in other words, up until k-1) whose AND value was l.
    # According to our storage array,
    # the number of pairs is storage[k-1][l]
    for l in range(len(storage)):
        if l & A[k] == 0: counts += storage[k-1][l]
print(counts) # Outputs 82
Related Question