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

Objective: Given a sorted array of positive integers, find out the smallest integer which cannot be represented as the sum of any subset of the array

Input: A Sorted Array

Output: The smallest number which cannot be represented as the sum of any subset of the given array

Examples :

```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 variable “smlNumber” and assign 1 to it.
• Now we need to find the gap between the array elements which cannot be represented as sum of any subset of array.
• To find that keep adding the array elements to smlNumber and check it current array element and if at any point smlNumber<current array element that means we have found the gap. return smlNumber.
• See figure

The smallest number which cannot be represented as the sum of any subset of the given array

Complete 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```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

### 1 Response

1. Sathiyaseelan says:

http://stackoverflow.com/questions/21060873/minimum-sum-that-cant-be-obtained-from-a-set

Implementation may be simple. but to understand how it works. the above link is helpful

This site uses Akismet to reduce spam. Learn how your comment data is processed.