# Find the minimum subset of a set of numbers with product divisible by a given integer

The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
Problem Statement:
You have an array $$a$$ of $$n$$ integers and an integer $$k$$. Your task is to find a subset $$m$$ of a where the following 2 conditions hold:
1) $$\prod\limits_{x\in m}x \equiv 0\mod k$$.
2) Size of $$m$$ is minimal possible (size of $$m \gt 0$$).

Constraints:
$$1 \le n \le 10^4$$
$$1 \le a_i \le 10^9$$
$$2 \le k \le 10^9$$
Time Limit = 3 seconds
Memory Limit = 256 MegaBytes

(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code. Thanks in advance :D)

• Please credit the original source where you encountered this task. Can you link to the original problem? (even if it is not in English) – D.W. Dec 30 '20 at 20:42
• Please do not re-post questions. – D.W. Dec 30 '20 at 20:45
• We've provided resources on how to approach dynamic programming tasks: cs.stackexchange.com/tags/dynamic-programming/info. Please study those materials, follow the systematic process outlined there, and then edit your question to show the progress you've made and at what stage you got stuck. – D.W. Dec 30 '20 at 20:49

1. Compute all the prime factors of $$k$$. It would take $$O(\sqrt{k})$$ time $$\approx$$ $$10^5$$ time. Note that, there could be at most $$10$$ different prime factors of $$k$$ since considering the $$10$$ smallest prime numbers gives the product: $$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$$ which exceeds $$10^9$$. Let us call the prime factors of $$k$$ as: $$f_{1}, \dotsc,f_{10}$$ with multiplicities $$m_{1}, \dotsc,m_{10}$$, respectively. The sum of multiplicities (or total number of prime factors) $$\sum_{i = 1}^{10}m_{i}$$ could be at most $$30$$ since $$2^{30}$$ exceeds $$10^{9}$$.
2. Now, you also need to factorize the numbers given in array $$a$$. However, you do not need to obtain all its factors. You just need to obtain the factors which are among $$f_{1},\dotsc,f_{10}$$ since other prime factors are irrelevant for $$\prod\limits_{x\in m}x \equiv 0\mod k$$. Therefore, just check that if an array entry $$a[j]$$ is divisible by some factors $$f_{i}$$ (obtained in step 2) and obtain its multiplicity in $$a[j]$$. Let $$m_{i}^{j}$$ denote the multiplicity of factor $$f_{i}$$ for an array entry $$a[j]$$. Computing all $$m_{i}^{j}$$ would take at most $$\sum_{i = 1}^{10}m_{i} \cdot n = 30 \cdot n$$ time $$\approx 10^{6}$$ time.
3. Now, you just need a Dynamic Programming approch to obtain the minimum value on size of $$m$$. Let $$A$$ denote a matrix of dimension $$(m_{1}+1)$$x $$(m_{2}+1)$$ x $$\dotsc$$x $$(m_{10}+1)$$ x $$n$$ such that an entry $$A[j_{1}][j_{2}] \dotsc[j_{10}][t]$$ denote the minimum size value of $$m$$ such that $$\prod\limits_{x\in m}x \equiv 0\mod k'$$ for $$m \subseteq \{a_{1},\dotsc,a_{t}\}$$ and $$k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$$. In otherwords, $$k'$$ is composed of all possible combinations of the factors $$f_{1}, \dotsc,f_{10}$$. Therefore $$k'$$ can take at most $$(m_{1}+1) \cdot (m_{2}+1) \dotsc (m_{10}+1) \approx 2^{10} \approx 10^{3}$$ different values. This bound is based on the assumption that all $$10$$ factors are distinct. If all the factors are the same the we have $$k' \leq 30$$ since $$2^{30}$$ exceeds $$10^9$$. So I believe $$k'$$ would take at most $$\approx 2 \cdot 2^{10} \approx 2 \cdot 10^3$$ different values.

Now, assuming 1 based indexing for the matrix $$A$$, we define the DP steps as follows.

The Main DP step:

$$A[j_{1}][j_{2}]\dotsc[j_{10}][t+1] = \min \left\{\begin{array}{lr} A[j_{1}][j_{2}]\dotsc[j_{10}][t], & \textrm{do not pick a[t+1]}\\ 1 + A[j_{1}-m_{1}^{t}][j_{2}-m_{2}^{t}]\dotsc[j_{10}-m_{10}^{t}][t], & \textrm{pick a[t+1]}\\ \end{array}\right.$$

The Base Step:

$$A[j_{1}][j_{2}]\dotsc[j_{10}][1] = 1$$ if $$j_{i} \leq m_{i}^{1}$$ for all $$1 \leq i \leq 10$$. And $$A[j_{1}][j_{2}]\dotsc[j_{10}][1] = \infty$$ otherwise. Here $$\infty$$ means that it is not possible to satisfy the constraint $$\prod\limits_{x\in m}x \equiv 0\mod k'$$ given $$m \subseteq \{a_{1} \}$$ and $$k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$$.

The Required Ouput:

The output of the DP procedure would be the solution: $$A[m_{1}][m_{2}]\dotsc[m_{10}][n]$$ which naturally denote the minimum size value of $$m$$ such that $$\prod\limits_{x\in m}x \equiv 0\mod k'$$ for $$m \subseteq \{a_{1},\dotsc,a_{n}\}$$ and $$k' = k = \prod_{i = 1}^{10} m_{i} \cdot f_{i}$$.

Running Time Analysis of DP:

The size of the matrix $$A$$ is $$(\textrm{number of possible value of k'}) \cdot n \approx 2 \cdot 10^3 \cdot 10^4 \approx 2 \cdot 10^{7}$$. Computing each entry takes 2 or 3 operations. Therefore total running time would be $$\approx 6 \cdot 10^7$$.

Thus the overall running time is $$\approx 10^5 + 10^6 + 6 \cdot 10^ 7 \approx 10^8$$. I have done the loose analysis, so it should be doable in 3 sec.

Total Space Complexity $$\approx$$ size of the matrix $$A$$ $$\approx 2 \cdot 10^7$$

I am the author of this problem and it was problem B in my contest. I have written an editorial here with the normal DP solution to get the 50 points and the coordinate compression DP which would get the 100 points.

• (A pity you can't comment (yet). OTOH, this non-answer to this non-question is more likely to survive here than on other SE sites.) – greybeard Dec 31 '20 at 11:35