Minimum number greater than the maximum of array which cannot be formed using the numbers in the array | 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
< ? php function findNumber ( $ arr , $ n ) { sort ( $ arr ) ; $ max = $ arr [ $ n - 1 ] ; $ table = array ( ( 2 * $ max ) + 1 ) ; $ table [ 0 ] = 0 ; for ( $ i = 1 ; $ i < ( 2 * $ max ) + 1 ; $ i ++ ) $ table [ $ i ] = PHP_INT_MAX ; $ ans = -1 ; for ( $ i = 1 ; $ i < ( 2 * $ max ) + 1 ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { if ( $ arr [ $ j ] <= $ i ) { $ res = $ table [ $ i - $ arr [ $ j ] ] ; if ( $ res != PHP_INT_MAX && $ res + 1 < $ table [ $ i ] ) $ table [ $ i ] = $ res + 1 ; } } if ( $ i > $ arr [ $ n - 1 ] && $ table [ $ i ] == PHP_INT_MAX ) { $ ans = $ i ; break ; } } return $ ans ; } { $ arr = array ( 6 , 7 , 15 ) ; $ n = sizeof ( $ arr ) ; echo ( findNumber ( $ arr , $ n ) ) ; }