Count numbers less than N containing digits from the given set : Digit DP | Python3 implementation to find the count of numbers possible less than N , such that every digit is from the given set of digits ; Function to convert integer into the string ; 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
import numpy as np ; NEW_LINE dp = np . ones ( ( 15 , 2 ) ) * - 1 ; NEW_LINE def convertToString ( num ) : NEW_LINE INDENT return str ( num ) ; NEW_LINE DEDENT def calculate ( pos , tight , D , sz , num ) : NEW_LINE INDENT if ( pos == len ( num ) ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( dp [ pos ] [ tight ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ tight ] ; NEW_LINE DEDENT val = 0 ; NEW_LINE if ( tight == 0 ) : NEW_LINE INDENT for i in range ( sz ) : NEW_LINE INDENT if ( D [ i ] < ( ord ( num [ pos ] ) - ord ( '0' ) ) ) : NEW_LINE INDENT val += calculate ( pos + 1 , 1 , D , sz , num ) ; NEW_LINE DEDENT elif ( D [ i ] == ord ( num [ pos ] ) - ord ( '0' ) ) : NEW_LINE INDENT val += calculate ( pos + 1 , tight , D , sz , num ) ; NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT for i in range ( sz ) : NEW_LINE INDENT val += calculate ( pos + 1 , tight , D , sz , num ) ; NEW_LINE DEDENT DEDENT dp [ pos ] [ tight ] = val ; NEW_LINE return dp [ pos ] [ tight ] ; NEW_LINE DEDENT def countNumbers ( D , N , sz ) : NEW_LINE INDENT num = convertToString ( N ) ; NEW_LINE length = len ( num ) ; NEW_LINE ans = calculate ( 0 , 0 , D , sz , num ) ; NEW_LINE for i in range ( 1 , length ) : NEW_LINE INDENT ans += calculate ( i , 1 , D , sz , num ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT sz = 3 ; NEW_LINE D = [ 1 , 4 , 9 ] ; NEW_LINE N = 10 ; NEW_LINE print ( countNumbers ( D , N , sz ) ) ; NEW_LINE DEDENT