Count numbers from a given range whose product of digits is K | Python 3 program to implement the above approach ; Function to count numbers in the range [ 0 , X ] whose product of digit is K ; If count of digits in a number greater than count of digits in X ; If product of digits of a number equal to K ; If overlapping subproblems already occurred ; Stores count of numbers whose product of digits is K ; Check if the numbers exceeds K or not ; Iterate over all possible value of i - th digits ; if number contains leading 0 ; Update res ; Update res ; Return res ; Utility function to count the numbers in the range [ L , R ] whose prod of digits is K ; Stores numbers in the form of string ; Stores overlapping subproblems ; Stores count of numbers in the range [ 0 , R ] whose product of digits is k ; Update str ; Stores count of numbers in ; the range [ 0 , L - 1 ] whose product of digits is k ; Driver Code
M = 100 NEW_LINE def cntNum ( X , i , prod , K , st , tight , dp ) : NEW_LINE INDENT end = 0 NEW_LINE if ( i >= len ( X ) or prod > K ) : NEW_LINE INDENT if ( prod == K ) : NEW_LINE return 1 NEW_LINE else : NEW_LINE return 0 NEW_LINE DEDENT if ( dp [ prod ] [ i ] [ tight ] [ st ] != - 1 ) : NEW_LINE INDENT return dp [ prod ] [ i ] [ tight ] [ st ] NEW_LINE DEDENT res = 0 NEW_LINE if ( tight != 0 ) : NEW_LINE INDENT end = ord ( X [ i ] ) - ord ( '0' ) NEW_LINE DEDENT for j in range ( end + 1 ) : NEW_LINE INDENT if ( j == 0 and st == 0 ) : NEW_LINE INDENT res += cntNum ( X , i + 1 , prod , K , False , ( tight & ( j == end ) ) , dp ) NEW_LINE DEDENT else : NEW_LINE INDENT res += cntNum ( X , i + 1 , prod * j , K , True , ( tight & ( j == end ) ) , dp ) NEW_LINE DEDENT DEDENT dp [ prod ] [ i ] [ tight ] [ st ] = res NEW_LINE return res NEW_LINE DEDENT def UtilCntNumRange ( L , R , K ) : NEW_LINE INDENT global M NEW_LINE str1 = str ( R ) NEW_LINE dp = [ [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 2 ) ] for k in range ( M ) ] for l in range ( M ) ] NEW_LINE cntR = cntNum ( str1 , 0 , 1 , K , False , True , dp ) NEW_LINE str1 = str ( L - 1 ) NEW_LINE dp = [ [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 2 ) ] for k in range ( M ) ] for l in range ( M ) ] NEW_LINE cntR = 20 NEW_LINE cntL = cntNum ( str1 , 0 , 1 , K , False , True , dp ) NEW_LINE return ( cntR - cntL ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = 20 NEW_LINE R = 10000 NEW_LINE K = 14 NEW_LINE print ( UtilCntNumRange ( L , R , K ) ) NEW_LINE DEDENT