Be the first user to complete this post

  • 0
 Add to List
Medium

49. Find the Unreachable Minimum in Array Subsets

Objective: Given a sorted array of positive integers, find the smallest integer that cannot be represented as the sum of any subset of the 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 the sum of any subset of the array.
  • To find that keep adding the array elements to smlNumber and check its current array element and if at any point smlNumber<current array element that means we have found the gap. print smlNumber.
	Array {1,2,6,7,9}
	Here we can make 1,2,3(2+1).
	Next Smallest number you can make is 6 and then 7(6+1).
	NO WAY you can make 4 and 5. since 5>4, 4 is our answer.

	i=0, arrA[0] =1, smlNo =1
	 arrA[0] <=smlNo (1<=1) so smlNo += arrA[0] = 1+1 = 2
	i=1, arrA[1] =2, smlNo = 2
	 arrA[1] <=smlNo (2<=2) sp smlNo += arrA[1] = 2+2 = 4
	i=2, arrA[2] =6, smlNo = 4 
	arrA[2] > smlNo (6>4), break, print smlNo (4).

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

Related Problems: