Count numbers less than N containing digits from the given set : Digit DP | JavaScript implementation to find the count of numbers possible less than N , such that every digit is from the given set of digits ; Recursive function to find the count of numbers possible less than N , such that every digit is from the given set of digits ; Base case ; Condition when the subproblem is computed previously ; Condition when the number chosen till now is definietly smaller than the given number N ; Loop to traverse all the digits of the given set ; Loop to traverse all the digits from the given set ; Store the solution for current subproblem ; Function to count the numbers less then N from given set of digits ; Converting the number to string ; Find the solution of all the number equal to the length of the given number N ; Loop to find the number less in in the length of the given number ; Driver Code ; Function Call
var dp = Array . from ( Array ( 15 ) , ( ) => Array ( 2 ) . fill ( - 1 ) ) ; function calculate ( pos , tight , D , sz , num ) { if ( pos == num . length ) return 1 ; if ( dp [ pos ] [ tight ] != - 1 ) return dp [ pos ] [ tight ] ; var val = 0 ; if ( tight == 0 ) { for ( var i = 0 ; i < sz ; i ++ ) { if ( D [ i ] < ( num [ pos ] - ' ' ) ) { val += calculate ( pos + 1 , 1 , D , sz , num ) ; } else if ( D [ i ] == num [ pos ] - ' ' ) val += calculate ( pos + 1 , tight , D , sz , num ) ; } } else { for ( var i = 0 ; i < sz ; i ++ ) { val += calculate ( pos + 1 , tight , D , sz , num ) ; } } return dp [ pos ] [ tight ] = val ; } function countNumbers ( D , N , sz ) { var num = ( N . toString ( ) ) ; var len = num . length ; var ans = calculate ( 0 , 0 , D , sz , num ) ; for ( var i = 1 ; i < len ; i ++ ) ans += calculate ( i , 1 , D , sz , num ) ; return ans ; } var sz = 3 ; var D = [ 1 , 4 , 9 ] ; var N = 10 ; document . write ( countNumbers ( D , N , sz ) ) ;