Minimum number of AND operations to make all array elements zero

Question

I came across this question in a programming contest:

We are given an array consisting of n elements. At each iteration, you can select any two elements a_i and a_j and replace a_i with a_i & a_j. & is the bitwise AND operator. Find the minimum number of AND operations needed to make all array elements zero.

Suppose that there is a solution for the given inputs. What is the optimal solution for this problem?

Edit: I've added my DP solution for the problem which takes more than 1 second to run. Any suggestion for speeding it up?

0 < n < 65535

D: maximum number of digits in base 2 (0 < D < 17)

GOAL: 2^D - 1

T[i][X] => minimum number of elements from {n_0, n_1, ..., n_i} that make X zero

T[i][0] = 0

T[0][X>0] = INF

T[i][X] = min( 1 + T[i-1][X & n_i] , T[i-1][X] )

T[n][GOAL] -> min number of AND operations

Answer 1

This seems to me like the set cover problem. We need to find the smallest subset that covers zeros in every position. Once that subset is found, the "absolute" zero that's generated can be used to convert other elements to zero. In the example below, any of the three elements in the subset can be used to become the first zero.

1001
0101<
0011<
1110<
0111

Answer 2

If the problem has a solution for a given input, you can perform these operations:

1. Choose an index i between [0,n-1](assuming array indexing is zero based).

2. For every j between 0 and n that is not i, perform a_i <- a_i & a_j. At this point you are guaranteed a_i equals 0, otherwise the problem is unsolveable because you performed bitwise and on all items in the array.

3. For every j between 0 and n that is not i, perform a_j <- a_i & a_j. This performs and on all items in the array with 0, making them 0 also.

You perform the and operation n-1 times for the first loop and n-1 times for the second loop, so in total 2n-2 and operations.

Edit:

This is assuming you cannot look at the values in the array.

Answer 3

My guess is that you can get the needed speedup by making your DP table sparse. We can think of the resulting algorithm as doing a breadth-first search from 2^D-1 to 0 on a graph where the nodes are 0..2^D-1 and the edges go from x to x&y where y is an array element. In fact, due to the commutativity/associativity of bitwise AND, we can tighten the edge set by requiring that x&y clear the lowest bit set in x. In the Python code below, this is achieved somewhat efficiently by using a map zero_index, but in C I would use an array (and replace the sets with bitmaps or arrays as appropriate).

import collections
import random


def min_and(seq):
    lst = list(seq)
    zero_index = collections.defaultdict(lambda: set(lst))
    for x in lst:
        y = x
        while y:
            zero_index[y & ~(y - 1)].discard(x)
            y &= y - 1
    visited = set()
    fringe = set(lst)
    i = 0
    while 0 not in fringe:
        visited.update(fringe)
        fringe = {
            x & y
            for x in fringe for y in zero_index[x & ~(x - 1)]
            if x & y not in visited
        }
        i += 1
    return i + len(lst) - 1


print(min_and(
    random.randrange(2**18) | random.randrange(2**18) | random.randrange(2**18)
    for i in range(100)))