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

Photo by Kelly Sikkema on Unsplash
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

Optimized approach:

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

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

Full Stack Programmer, love to solve problem’s during free time.