Minimum number greater than the maximum of array which cannot be formed using the numbers in the array | C ++ implementation of the approach ; Function that returns the minimum number greater than maximum of the array that cannot be formed using the elements of the array ; Sort the given array ; Maximum number in the array ; table [ i ] will store the minimum number of elements from the array to form i ; Calculate the minimum number of elements from the array required to form the numbers from 1 to ( 2 * max ) ; If there exists a number greater than the maximum element of the array that can be formed using the numbers of array ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findNumber ( int arr [ ] , int n ) { sort ( arr , arr + n ) ; int max = arr [ n - 1 ] ; int table [ ( 2 * max ) + 1 ] ; table [ 0 ] = 0 ; for ( int i = 1 ; i < ( 2 * max ) + 1 ; i ++ ) table [ i ] = INT_MAX ; int ans = -1 ; for ( int i = 1 ; i < ( 2 * max ) + 1 ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( arr [ j ] <= i ) { int res = table [ i - arr [ j ] ] ; if ( res != INT_MAX && res + 1 < table [ i ] ) table [ i ] = res + 1 ; } } if ( i > arr [ n - 1 ] && table [ i ] == INT_MAX ) { ans = i ; break ; } } return ans ; } int main ( ) { int arr [ ] = { 6 , 7 , 15 } ; int n = ( sizeof ( arr ) / sizeof ( int ) ) ; cout << findNumber ( arr , n ) ; return 0 ; }