1
$\begingroup$

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ elements of $A$ in $O(n^2)$ or $O(n^3)$ time complexity? If yes what would be the pseudocode?

This seems to be a knapsack problem to me and according to Wikipedia it's an NP-complete problem. So even if the array was unsorted in the first place and we wanted to sort it it would take $O(n\log n)$ time which doesn't really help if the problem is NP-complete anyway. Yet I wonder if some optimization may be made to achieve better time.

Please treat $x$ and $k$ as constants, for running time analysis.

$\endgroup$
  • 1
    $\begingroup$ All algorithms will clearly be constant-time, in terms of n. $\endgroup$ – Acccumulation Jun 15 '18 at 18:31
  • $\begingroup$ What's $n$? Is $k$ to be treated as a constant? Is $x$ to be treated as a constant? $\endgroup$ – D.W. Jun 15 '18 at 19:08
  • $\begingroup$ What's the context where you encountered this problem? Can you credit the original source? $\endgroup$ – D.W. Jun 15 '18 at 19:08
  • $\begingroup$ @D.W. I edited the OP to add that $n$ is the length of the array. I did say in the OP that $x$ is a positive integer and also "$k$ elements of $A$" so yes they're constants. This is a personal question of mine so no source for it. $\endgroup$ – Yos Jun 15 '18 at 19:17
1
$\begingroup$

It depends on the numbers in the array. For example if all array elements are positive integers, and the requested sum is S, then O(nS) is easy.

$\endgroup$
  • 1
    $\begingroup$ The question says they're all positive integers, but it's not clear that we can treat $S$ as a constant. $\endgroup$ – David Richerby Jun 15 '18 at 17:59
  • $\begingroup$ S doesn't have to be constant, it's still O (nS). $\endgroup$ – gnasher729 Jun 15 '18 at 22:24
  • $\begingroup$ Sure but the question asks if it's possible in $O(n^2)$ or $O(n^3)$. If $S$ is part of the input, then $nS = O(n2^n)$ is about the best you can say (unless it's written in unary, in which case you get $O(n^2)$, as requested. $\endgroup$ – David Richerby Jun 15 '18 at 22:42
1
$\begingroup$

If $x$ and $k$ are to be treated as constants, as you propose, then there is a solution with running time $O(n)$: use dynamic programming, and let $B[s,i,j]$ indicate whether there is a combination of $i$ elements from $A[1..j]$ that sums to $s$. The $B$ array can be filled in, in $O(nkx)=O(n)$ time, using dynamic programming.

In practice I'm skeptical that one can reasonably consider $x,k$ to be constants; unless $x,k$ are particularly small, calling this $O(n)$ running time might give a misleading impression about how fast it will be.

$\endgroup$
1
$\begingroup$

If you allow to use every number from the array only once then it is indeed a knapsack problem. If you can use every number multiple times then you consecutively generate sets of number which can be generated with sums of 1, 2, 3 ... k elements of the array. Every step is O(n*x). Overall complexity will be O(k*n*x).

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