Tag Info

1

I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size). Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset. You could even account for duplicates by instead using ...

1

You can solve this problem with the inclusion exclusion principle. Assume you have two subsets $S_1, S_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S_1$ multiplied by the number of ways of choosing an element from $S_2$ minus the number of ways of choosing the same number from $S_1$ and $S_2$. Now given ...

1

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$. Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe ...

0

The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one. So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set ...

Top 50 recent answers are included