Minimum number of single digit primes required whose sum is equal to N | function to check if i - th index is valid or not ; function to find the minimum number of single digit prime numbers required which when summed up equals to a given number N . ; Not possible ; Driver Code
< ? php function check ( $ i , $ val ) { if ( $ i - $ val < 0 ) return false ; return true ; } function MinimumPrimes ( $ n ) { for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ dp [ $ i ] = 1e9 ; $ dp [ 0 ] = $ dp [ 2 ] = $ dp [ 3 ] = $ dp [ 5 ] = $ dp [ 7 ] = 1 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { if ( check ( $ i , 2 ) ) $ dp [ $ i ] = min ( $ dp [ $ i ] , 1 + $ dp [ $ i - 2 ] ) ; if ( check ( $ i , 3 ) ) $ dp [ $ i ] = min ( $ dp [ $ i ] , 1 + $ dp [ $ i - 3 ] ) ; if ( check ( $ i , 5 ) ) $ dp [ $ i ] = min ( $ dp [ $ i ] , 1 + $ dp [ $ i - 5 ] ) ; if ( check ( $ i , 7 ) ) $ dp [ $ i ] = min ( $ dp [ $ i ] , 1 + $ dp [ $ i - 7 ] ) ; } if ( $ dp [ $ n ] == ( 1e9 ) ) return -1 ; else return $ dp [ $ n ] ; } $ n = 12 ; $ minimal = MinimumPrimes ( $ n ) ; if ( $ minimal != -1 ) { echo ( " Minimum ▁ number ▁ of ▁ single ▁ " . " digit ▁ primes ▁ required ▁ : " ) ; echo ( $ minimal ) ; } else { echo ( " Not ▁ possible " ) ; } ? >