# 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: 2Input:  arr[] = {1, 1, 1, 1};Output: 5Input:  arr[] = {1, 1, 3, 4};Output: 10Input:  arr[] = {1, 2, 5, 10, 20, 40};Output: 4Input:  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. If ‘1’ is missing, then we can immediately return ‘1’. But if ‘1’ is indeed present at a, 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 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  at position a being added into the mix. So that means, now we can create 5 consecutive positive integers:

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

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

But a 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 ≤ (max(10) + 1) (i.e. 8 < 11). Since this condition is satisfied, the sequence can be furthered to: max + a = 10 + 8 = 18 which becomes the new max.

Now when we looking for a value ≤ 19 (18+1) in a, 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.

--

--