# Minimum number that cannot be formed by any subset of an array

Objec­tive: Given a sorted array of pos­i­tive inte­gers, find out the small­est inte­ger which can­not be rep­re­sented as the sum of any sub­set of the array

Input: A Sorted Array

Out­put: The small­est num­ber which can­not be rep­re­sented as the sum of any sub­set of the given array

Exam­ples :

```Array {1,1,3,4,6,7,9} smallest Number : 32
Array {1,1,1,1,1} smallest Number : 6
Array {2,3,6,7} smallest Number : 1
Array {1,2,6,7,9} smallest Number : 4
```

Approach:

• If 1 is not present in the array, our answer is 1.
• So take a vari­able “sml­Num­ber” and assign 1 to it.
• Now we need to find the gap between the array ele­ments which can­not be rep­re­sented as sum of any sub­set of array.
• To find that keep adding the array ele­ments to sml­Num­ber and check it cur­rent array ele­ment and if at any point sml­Num­ber<cur­rent array ele­ment that means we have found the gap. return sml­Num­ber.
• See fig­ure

The small­est num­ber which can­not be rep­re­sented as the sum of any sub­set of the given array

Com­plete Code:

```Output:
Smallest Positive Integer that cant be represented by the sum of any subset of following arrays are :

{1,1,3,4,6,7,9} - 32
{1,1,1,1,1} -> 6
{2,3,6,7} -> 1
{1,2,6,7,9} -> 4```