Find the smallest positive integer that can not be formed from the sum of numbers from array.

Input:  arr[] = {1, 3, 6, 10, 11, 15};
Output: 2

Input: arr[] = {1, 1, 1, 1};
Output: 5

Input: arr[] = {1, 1, 3, 4};
Output: 10

Input: arr[] = {1, 2, 5, 10, 20, 40};
Output: 4

Input: arr[] = {1, 2, 3, 4, 5, 6};
Output: 22

Solution:

A Simple Solution is to start from value 1 and check all values one by one if they can sum to values in the given array. This solution is very inefficient.

Optimized approach:

Now let’s try to solve it in O(n).:

First we can check whether ‘1’ is present in the array or not at position a[0]. If ‘1’ is missing, then we can immediately return ‘1’. But if ‘1’ is indeed present at a[0], then we can safely initialize ‘max’ 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 max is = 2.

We move to next index , 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

We have processed till a[2] and max 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 ≤ (max(5) + 1), so we can still continue extending our string of consecutive integers to max+nextValue = 5+5 = 10. And that makes max = 10.

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

Now when we looking for a value ≤ 19 (18+1) in a[5], we find 21, leaving a gap of two numbers [19,20].

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

Implementation :

Complexity:

Time complexity O(n) as we traverse the entire input and space complexity O(1), without any extra space.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store