Krdytkyu

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?

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