Find the numbers from 1 to N that contains exactly k non | Function to find number less than N having k non - zero digits ; Store the memorised values ; Initialise ; Base ; Calculate all states For every state , from numbers 1 to N , the count of numbers which contain exactly j non zero digits is being computed and updated in the dp array . ; Return the required answer ; Driver code ; Function call
function k_nonzero_numbers ( s , n , k ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i <= n ; i ++ ) { dp [ i ] = new Array ( 2 ) ; for ( let j = 0 ; j < 2 ; j ++ ) { dp [ i ] [ j ] = new Array ( k + 1 ) ; for ( let x = 0 ; x <= k ; x ++ ) dp [ i ] [ j ] [ x ] = 0 ; } } dp [ 0 ] [ 0 ] [ 0 ] = 1 ; for ( let i = 0 ; i < n ; ++ i ) { let sm = 0 ; while ( sm < 2 ) { for ( let j = 0 ; j < k + 1 ; ++ j ) { let x = 0 ; while ( x <= ( sm != 0 ? 9 : s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) { if ( j + ( x > 0 ? 1 : 0 ) < k + 1 ) { dp [ i + 1 ] [ ( sm != 0 || x < ( s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) ? 1 : 0 ] [ j + ( x > 0 ? 1 : 0 ) ] += dp [ i ] [ sm ] [ j ] ; } ++ x ; } } ++ sm ; } } return dp [ n ] [ 0 ] [ k ] + dp [ n ] [ 1 ] [ k ] ; } let s = " " ; let k = 2 ; let n = s . length ; document . write ( k_nonzero_numbers ( s , n , k ) ) ;