# Minimum number that cannot be formed by any subset of an array

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.

You can pre compute an array $B$ such that $B=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.
• 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 Aug 1, 2014 at 17:26