1
$\begingroup$

We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP approach, and outputing the min number with value infinity. But the problem is that the sum of ranges can be as large as 109, and we have about 105 queries of the type $[L,R]$, so I was hoping there'd be a better approach. Can anyone point me in the right direction?

There are 105 elements in the array

Suppose the elements of the array are 1,1,2,7. Then for indices 1 and 4, the smallest number that cannot be formed as a sum is 5. since we can form all 1,2,3,4.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

You can pre compute an array $B$ such that $B[0]=0$ and $B[i]=B[i-1]+A[i-1]$. That you can use $A[L,R]=B[R+1]-B[L]$ to speed up you computations.

Now you can enumerate all pairs $A[L,R]$ and insert them into some sorted data structure $T$, and then you will be able to enumerate all of them in a sorted fashion, and thus answer your question.

This will still be in complexity $O(n^2\log n)$ where $n$ is the size of $A$ but it will not change even if the numbers in $A$ are large. This is not fundamentally faster than proposed solution, I don't know if there is indeed a faster one.

$\endgroup$
2
  • $\begingroup$ since there are 10^5 elements in this array, I don't think this will be feasible either. $\endgroup$
    – Alice
    Jan 11, 2014 at 10:42
  • $\begingroup$ If the sum of the ranges was smaller, you could achieve a faster runtime using FFT. Given $\mathcal{O}(S) = \mathcal{O}(n)$, where $S$ is the maximum sum, the algorithm runs in $\mathcal{O}(n \log{n})$. The basic idea is that you can get all of the subarray sums by subtracting $B$ from itself. This can be done with an FFT if you represent $B$ as exponents of a polynomial. See: discuss.codechef.com/questions/18331/farasa-editorial $\endgroup$
    – Michael Xu
    Aug 1, 2014 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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