-2
$\begingroup$

You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$.

Is there an efficient algorithm to solve the above problem. We can assume $1\le n \le 10^5$ and $1\le A_i \lt k \le 10^9$ for each element $A_i$ in $A$.

$\endgroup$

closed as unclear what you're asking by Juho, Evil, David Richerby, Discrete lizard Mar 4 at 9:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Have you read how to ask a good homework question?? The problem in the question can be considered as a homework question. Besides a thoughtful question, it is expected of you to show your partial progress, thoughts or where you got stuck. It will help draw more better answers faster. Otherwise, this post might be closed or downvoted, as posts that simply dump problems are discouraged. This site is designed as a knowledge sharing question and answer forum instead of a solution rendering service. $\endgroup$ – Apass.Jack Mar 1 at 17:13
  • $\begingroup$ This GeeksforGeeks post gives an $O(n2^{n/2})$ solution, but unfortunately it does not work in your case since your $n$ is too large. $\endgroup$ – xskxzr Mar 1 at 17:33
  • $\begingroup$ @xskxzr this problem can be solved easily. Note that the problem is about the number of subsets with product less than $k$, where $k\le10^9$, instead of $k$-th largest subset sum. $\endgroup$ – Apass.Jack Mar 1 at 18:41
  • $\begingroup$ Since we can extract integers with values 0 and 1 from the problem, we can assume all integers have values ≥ 2, so we have products of no more than 29 integers, meaning this can be solved in O (n^29). $\endgroup$ – gnasher729 Mar 1 at 21:37
  • $\begingroup$ Can you edit the question to add a reference to the original source of the problem? $\endgroup$ – D.W. Mar 3 at 22:56
3
$\begingroup$

As Apass.Jack suggested in the comment, there is an $O\left(n\left(\log n+\sqrt{k}\right)\right)$ solution based on dynamic programming.

First we sort the array to get $a_{11},a_{12},\ldots,a_{1n_1},\ldots,a_{2n_2},\ldots,a_{tn_1},\ldots,a_{tn_t}$ where $a_{11}=\cdots=a_{1n_1}<a_{21}=\cdots=a_{2n_2}<\cdots<a_{t1}=\cdots=a_{tn_t}$.

Let $c(m,p)$ be the number of subsets with product less than or equal to $p$ when only considering the elements from $a_{11}$ to $a_{mn_m}$. By counting separately the subsets containing how many $a_{m1}$'s, we have the following recurrence:

$$ c(m,p)=\sum_{i=0}^{n_m} c\left(m-1,\left\lfloor \frac{p}{a_{m1}^i}\right\rfloor\right). $$

Note for positive integers $p,x,y$,

$$ \left\lfloor \frac{\left\lfloor \frac{p}{x}\right\rfloor}{y}\right\rfloor=\left\lfloor\frac{p}{xy}\right\rfloor, $$

to calculate $c(t,k)$, we only need to calculate $c(m,p)$ for all $m=1,2,\ldots,t$ and $p=\lfloor k/i\rfloor$ for $i=1,2,\ldots,k$. Note if $i> \sqrt{k}$, then $\lfloor k/i\rfloor\le \left\lfloor \sqrt{k}\right\rfloor$, so all possible values of $p$ are $$ 1,2,\ldots,\left\lfloor \sqrt{k}\right\rfloor,\left\lfloor \frac{k}{\left\lfloor\sqrt{k}\right\rfloor}\right\rfloor,\left\lfloor \frac{k}{\left\lfloor\sqrt{k}\right\rfloor-1}\right\rfloor,\ldots,\left\lfloor \frac{k}{1}\right\rfloor, $$ i.e., only $O(\sqrt{k})$ values. So we can calculate $c(t,k)$ in $O\left(n\sqrt{k}\right)$ time (why? It's left as an exercise), plus the time for sorting.

Denote the possible values of $p$'s by $p_1,p_2,\ldots$. Another notable thing is that to achieve the time complexity above, given $p$, we must find $i$ such that $p=p_i$ in constant time. This is easy. If $p\le \left\lfloor \sqrt{k}\right\rfloor$, then $i=p$. Otherwise assume $p=\lfloor k/x\rfloor$ for some integer $x\le \left\lfloor\sqrt{k}\right\rfloor<p$, then we have $x=\lfloor k/p\rfloor$, so we can assert $i=2\left\lfloor \sqrt{k}\right\rfloor+1-\lfloor k/p\rfloor$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.