The Interview Question Today#1 (24-2-19)

Question:

Find Minimum number that cannot be formed by Sum of any subset of an array
Input: A Sorted Array
Output: The smallest number which cannot be formed by any subset of an array
Example:
If Array[]={1,2,3,4,5};
Then the smallest number:16.

Solution:

      Approach/Method:

1.      Take a variable small and initialize it to 1

2.      Now Compare small with array current location (starts              with  0 index)

·    if it is not present our answer is small

·    else add array current location value to the small variable and  increment the location And jump back to step 2 Do is till u get smallest value.

3.      Example: Array[]={1,2,3,4,5}

i=0, array [0] =1, small=1, array [0] <=small (1<=1) => small=small+array [0] = 1+1=2

i++,i=1, array[1]=2, small=2, array[1] <=small (2<=2) => small= small+ array [1]= 2+2=4

i++,i=2, array[2]=3, small=4, array[2] <=small (3<=4) => small= small+ array [2]= 4+3=7

i++,i=3, array[3]=4, small=7, array[3] <=small (4<=7) => small= small+ array [3]= 7+4=11

i++,i=4,array[4]=5,small=11,array[4]<=small(5<=11)=>small=small+array[4]=11+5=16

small=16.

C program:

// C program to find the smallest positive value that cannot be

// represented as sum of subsets of a given sorted array

#include<stdio.h>
int getsmallest(int arr[], int n)
{
   int small = 1,i;
   for (i = 0; i < n; i++)
        if( arr[i] <= small)
       small = small + arr[i];
   return small;
}
int main()
{
   int arr[100],n,i;
   printf("Enter the no of elements u want to insert\n");
   scanf("%d",&n);
   printf("enter the elements in ascending order\n");
   for(i=0;i<n;i++){
    scanf("%d",&arr[i]);
   }
    printf("Smallest Element=%d",getsmallest(arr,n));
   return 0;
}

Output:

Enter the no of elements u want to insert

5

enter the elements in ascending order

1

2

3

4

5

Smallest Element=16