I have n boxes n <= 100. There are k fruits k <= 6 , which will be inserted one by one. each fruit will be putted into the different boxes. for each fruits there will array of zeros and ones where 1 represents that box contains this fruit and zero means that it doesn't contain fruit.

I have to find out how many minimum boxes do I need to uniquely identify the given fruits.

For example : lets say there are 2 fruits and 9 boxes.

Box No's: 1 2 3 4 5 6 7 8 9

Fruit A : 1 1 1 1 0 0 0 1 0

Fruit B : 1 0 0 0 1 0 1 1 1

If we choose box such as 2,3,4,5,7,9 any one of them can uniquely identify the given fruits because one exist and other don't. So answer here is 1.

Lets add another fruit here C:

0 1 0 1 1 1 1 0 1

If you choose any of the above boxes , then you will have conflict and cannot uniquely identify the given fruits.So you will need another box here. Minimum Answer would be 2 here.

So far I have done that for each box i will put it into the box. then for all boxes we will have some set , element in it say that there is fruit[i] in it.

So I would have to find out minimum boxes such that if we take subset of those and do intersection of that subset and intersection comes out to be fruit[i] then we can uniquely identify that given fruit.

But I am stuck on how would I find the minimum boxes .

Can anyone tell whether even my approach is right or wrong ?

Any help or algorithm or any other approach to solve this problem.

Thanks in advance.