Minimum count of elements that sums to a given number | Java implementation of the above approach ; we will only store min counts of sum upto 100 ; initialize with INT_MAX ; memo [ 0 ] = 0 as 0 is made from 0 elements ; fill memo array with min counts of elements that will constitute sum upto 100 ; min_count will store min count of elements chosen ; starting from end iterate over each 2 digits and add min count of elements to min_count ; Driver code
class GFG { static int minCount ( int K ) { int memo [ ] = new int [ 100 ] ; for ( int i = 0 ; i < 100 ; i ++ ) { memo [ i ] = Integer . MAX_VALUE ; } memo [ 0 ] = 0 ; for ( int i = 1 ; i < 100 ; i ++ ) { memo [ i ] = Math . min ( memo [ i - 1 ] + 1 , memo [ i ] ) ; } for ( int i = 10 ; i < 100 ; i ++ ) { memo [ i ] = Math . min ( memo [ i - 10 ] + 1 , memo [ i ] ) ; } for ( int i = 25 ; i < 100 ; i ++ ) { memo [ i ] = Math . min ( memo [ i - 25 ] + 1 , memo [ i ] ) ; } int min_count = 0 ; while ( K > 0 ) { min_count += memo [ K % 100 ] ; K /= 100 ; } return min_count ; } public static void main ( String [ ] args ) { int K = 69 ; System . out . println ( minCount ( K ) ) ; } }