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.

3 Answers

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.

• since there are 10^5 elements in this array, I don't think this will be feasible either. Commented Jan 11, 2014 at 10:42
• 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 Commented Aug 1, 2014 at 17:26
def cannotForm(numbers):
numbers.sort()

min_count = 1

for number in numbers:
if min_count<number:
return min_count
min_count+=number
print(min_count)


Maybe try this code, it works on a complexity of O(N) utilising the fact that the minimum number that cannot be formed is actually the subsequence minimum between the two consecutive numbers N and N+K

The total complexity is O(NlogN) due to the sorting which is the dominant factor

Let's take the simplest array of size n

• A0[] = [1] where k = [1] => 1<1
• A1[] = [1,k] where k=[2,N] => 2<k
• A2[] = [1,k,k1] where k=k1=[3,N] & k<=k1 => k+2 < k1+1
• A3[] = [1,k,k1,k2] where k<=k1<=k2 => k1+k+2 < k2+1

hence, if it is observed, we are basically covering the maximum bounds for the subarray summation. Maximum subarray sum:(1+k+k1) and then doing (1+k+k1)+1 to find the term that has be covered by k2 and if it does not then that becomes the minimum sum that cannot be made

X = [1,1,2,7] --> (1+1+2) = 4 + 1 = 5 < 7 and hence, it cannot be formed by 7 since 7 > 5 and addition as a function is always monotonically increasing. That is, it always increases the value and so minimum missing value is 5 or it is (1+k+k1)+1 = (2+k+k1)

• This might work. 1. Can you prove your code correct? 2. Complexity should be $O(n \log n)$ to accommodate sorting.
– Kai
Commented May 13 at 5:18
• True, the dominant factor is the sorting algorithm. As far the prove is concern, let me see. I will add it in my explaination. Commented May 15 at 12:02
• After writing my answer, and spotting that it could be improved, I read this one - and it is absolutely correct. The complexity will usually be better than O(n log n). Use quicksort, but only partitioning the left half recursively. Then as long as the number <= min_number add it to min_number even if it is not the smallest. If that doesn’t work then sort the next few numbers. Commented May 15 at 21:50

Assuming L, R might be large: Extract all the elements from L to R and sort them, so you have n items in ascending order.

If the first one is x, then we have two possible sums 0 and x. X must be 1, or 1 is not a possible sum.

If the second one is y, then y = 1 and possible sums are 0 to 2, or y = 2 and possible sums are 0 to 3.

We repeat this and keep track of possible sums, taking advantage of the fact that possible sums are often complete ranges. If k items produce sums from 0 to m, then to produce m+1 you need to add a number from 1 <= z <= m+1, which produces all sums from 0 to z+m.