1
$\begingroup$

Suppose we are given an array $A[1\ldots n]$ and a value $C$.

Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots n]$ whose elements sum to at least $C$?

$\endgroup$
  • $\begingroup$ What do you mean by “smallest”? $\endgroup$ – Yuval Filmus Oct 13 at 9:31
  • $\begingroup$ the subset with the least elements $\endgroup$ – flutterbug98 Oct 13 at 9:46
  • $\begingroup$ I mean, the subset with smallest cardinality $\endgroup$ – flutterbug98 Oct 13 at 9:54
  • $\begingroup$ Have you tried the greedy approach? $\endgroup$ – Yuval Filmus Oct 13 at 9:57
  • $\begingroup$ I'm not really sure what the greed approach is $\endgroup$ – flutterbug98 Oct 13 at 9:58
1
$\begingroup$

First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$.

  • If $S=C$, then $Q$ is exactly the optimal subset we want.
  • If $S<C$, then the optimal subset is the union of $Q$ and the subset with smallest cardinality of $P$ whose elements sum to at least $C-S$, which can be found by recursively applying this algorithm on $P$.
  • If $S>C$, then the optimal subset is the subset with smallest cardinality of $Q$ whose elements sum to at least $C$, which can be found by recursively applying this algorithm on $Q$.

Let $T(n)$ denote the expected running time of this algorithm on an input of $n$ elements, we have $$T(n)\le \frac{1}{n-1}\sum_{i=1}^{n-1} T(\max\{i,n-i\})+cn,$$ where $c$ is a constant. By mathematical induction we can conclude that $T(n)\le 4cn$, thus the algorithm runs in expected linear time.


You can also use the idea of median-of-medians to get a worst-case linear time algorithm by selecting the pivot as the apporximate median produced by the median-of-medians algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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