[Solved]: Minimum number that cannot be formed by any subset of an array

Problem Detail: 

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 10⁹, and we have about 10⁵ 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 10⁵ 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.

Asked By : Alice

Answered By : jmad

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19651