-1
$\begingroup$

Let's say we have given array $A = \{a_1, a_2, a_3,\dots,a_n\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have sum greater or equal to $L$.

Example

$A = \{1, 2,3\}, L = 2$, in this case $K = 1$, because any subset of size $1$ will not affect the array, or the array sum will be greater or equal to $L$. Note that $K$ cannot be $2$ because the array without the subset $\{2, 3\}$ has sum $1$ which is less than $L$.

What I think for the solution

I started thinking about solution with dynamic programming, I'm thinking in the following way, if we have $K$ for first $x$ elements and for sum $y$, we could come with relation to solve for $x+1$ elements and for $y+1$ for value of $L$, but I cannot come with the relation.

$\endgroup$
1
$\begingroup$

The worst case will always be, as in your example, a subset that contains the biggest elements of the set. So I would

  1. order the set
  2. remove the biggest element and check if the condition still holds
  3. iterate 2.

The number of iterations will give you your K.

Runtime $O(N\cdot logN)$ or better for the sorting, $O(N)$ for computing the sum of the array, at most $O(N)$ iterations.

$\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.