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

by

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

Complete Code:

public class SmallestIntegerInSortedArray {
public int find(int [] arrA){
int smlNumber = 1;
for(int i = 0;i<arrA.length;i++){
if(arrA[i]<=smlNumber){
smlNumber += arrA[i];
}else{
break;
}
}
return smlNumber;
}
public static void main(String arg[]){
SmallestIntegerInSortedArray i = new SmallestIntegerInSortedArray();
System.out.println("Smallest Positive Integer that cant be represented by the sum of any subset of following arrays are : ");
int [] arrA = { 1,1,3,4,6,7,9};
System.out.println("{1,1,3,4,6,7,9} –" + i.find(arrA));
int [] arrB = {1,1,1,1,1};
System.out.println("{1,1,1,1,1} –" + i.find(arrB));
int [] arrC = {2,3,6,7};
System.out.println("{2,3,6,7} –" + i.find(arrC));
int [] arrD = {1,2,6,7,9};
System.out.println("{1,2,6,7,9} –"+ i.find(arrD));
}
}

view raw
SmallestIntegerInSortedArray.java
hosted with ❤ by GitHub 

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 Posts: