ELI5: Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

This is a problem with a tricky solution and I scoured the internet for a decent explanation of why the solution works but couldn’t find any. So I conferred with a friend over the solution and decided to share ‘why and how’ the solution works.
This is what I would like to call the “ELI5: Explain Like I’m 5” series.

Q: Given an array (sorted in non-decreasing order) of positive numbers, find the smallest positive integer value that cannot be represented as sum of elements of any subset of the given set.
Expected time complexity is O(n).

Original Question: GeeksForGeeks and CareerCup

The question can be posed slightly differently where in the given array might not be sorted to begin with, then we would have to sort it on our own in O(nlogn) time. For now, we will consider that we are operating on a sorted array.

Brute Force:

The question kinda gives away the brute force approach by suggesting subsets.

1. You can generate all possible 2^n subsets (n — number of elements in the array)
2. Compute the sum of each subset,
3. Insert those sums into a HashSet and then
4. Run a loop i: 1 → infinity to check if ‘i’ is present in the hashSet. The first element that is missing from the hashSet is our answer.

Generating subsets is an NP-Complete problem and so there is no polynomial time solution for it (yet). In fact, the time complexity of this approach: O(2^n)

Optimized approach:

Now let’s try to solve it in O(n). Consider the following sorted array ‘a’:

Let ‘maxPossible’ be a running variable which indicates the maximum possible number we can create by adding up any amount of numbers in the array. Our final answer would be ‘maxPossible+1’ as that would be the number which cannot be formed from the elements of the array.

Since the question asks us to find the smallest positive integer, we can check whether ‘1’ is present in the array or not at position a[0]. If ‘1’ is missing, then we can immediately say we found our answer and return ‘1’. But if ‘1' is indeed present at a[0], then we can safely initialize ‘maxPossible’ to ‘1’ as we can now at-least create ‘1' from the array.

Let’s move on to a[1] which is also ‘1’. So with these two ones, we can create 1 & 2, so our maxPossible at this point is 2.

Now comes the interesting part and this is where the algorithm takes off. We have two numbers [1, 2] which can be created and we have a new number [3] at position a[2] being added into the mix. So that means, now we can create 5 consecutive positive integers:

• [1, 2] that we already had
• [3] the new entrant solo entry
• [1, 2] + [3] = [4, 5] — new entrant being added to all the previous numbers

The Key:

A positive integer ‘k’ being added to a series of consecutive positive integers [1, 2, 3, …….. p] furthers that series by K elements without disrupting the continuity as long as k ≤ (p+1). This is just a formal way of stating what we observed in the diagram above where p = 2, k = 3 and the series now has 5 elements. Understanding and internalizing this property is the key to grokking this algorithm.

We have processed till a[2] and maxPossible is now ‘5’. If the next element in the input array a[3] were > 6 (say 7), then we would have our answer because then from [1, 2, 3, 4, 5] and [7]there’s no way to produce ‘6’.

But a[3] is 5 which is ≤ (maxPossible + 1), so we can still continue extending our string of consecutive integers to maxPossible+newEntrant = 5+5 = 10. And that makes maxPossible = 10.

We now check if the next element: a[4] ≤ (maxPossible + 1) (i.e. 8 < 11). Since this condition is satisfied, the sequence can be furthered to: maxPossible + a[4] = 10 + 8 = 18 which becomes the new maxPossible.

Now when we looking for a value ≤ 19 (18+1) in a[5], we hit a roadblock (or a jackpot, depends on how you see it) in that we find 21, leaving a gap of two numbers [19,20] which can’t be formed from [1,2,…..,18] + [21] (Remember the key property we discussed)

So that’s our answer: 19 (maxPossible + 1)

Here’s the code snippet to do that and hopefully it all makes sense now:

If you enjoyed this post, please share, comment, and press that 👏 a few times (up to 50 times). . . Maybe it will help someone.

PS: I’m thinking of carrying on this ELI5 series and if any of you have an algorithm/programming problem/CS concept for which you are struggling to find a decent explanation online, please leave a comment below and I will try to explain it in simpler terms.