Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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 smallest number which cannot be represented as the sum of any subset of the given array

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

You may also like...