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 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.
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^2log 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
