Minimum number of AND operations to make all array elements zero

  • A+
Category:Languages

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?

 


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 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: