CODEWITHSUNDEEP
algorithmdata-structuresdynamic-programminggreedy
Mbt925
Mbt925

Reputation: 1346

Minimum number of AND operations to make all array elements zero

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 ai and aj and replace ai with ai & aj. & 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

Upvotes: 6

Views: 2199

Answers (3)

David Eisenstat
David Eisenstat

Reputation: 65458

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)))

Upvotes: 3

Gregory
Gregory

Reputation: 99

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 ai <- ai & aj. 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 aj <- ai & aj. 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.

Upvotes: 4

גלעד ברקן
גלעד ברקן

Reputation: 23955

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

Upvotes: 8

Related Questions