Count numbers from a given range whose product of digits is K | Javascript 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 ; Initialize dp [ ] [ ] [ ] to - 1 ; Stores count of numbers in the range [ 0 , R ] whose product of digits is k ; Update str ; Initialize dp [ ] [ ] [ ] to - 1 ; Stores count of numbers in the range [ 0 , L - 1 ] whose product of digits is k ; Driver Code
let M = 100 ; function cntNum ( X , i , prod , K , st , tight , dp ) { if ( i >= X . length prod > K ) { return prod == K ? 1 : 0 ; } if ( dp [ prod ] [ i ] [ tight ] [ st ] != - 1 ) { return dp [ prod ] [ i ] [ tight ] [ st ] ; } let res = 0 ; let end = tight > 0 ? X [ i ] - ' ' : 9 ; for ( let j = 0 ; j <= end ; j ++ ) { if ( j == 0 && st == 0 ) { res += cntNum ( X , i + 1 , prod , K , 0 , ( tight & ( ( j == end ) ? 1 : 0 ) ) , dp ) ; } else { res += cntNum ( X , i + 1 , prod * j , K , 1 , ( tight & ( ( j == end ) ? 1 : 0 ) ) , dp ) ; } } return dp [ prod ] [ i ] [ tight ] [ st ] = res ; } function UtilCntNumRange ( L , R , K ) { let str = ( R ) . toString ( ) ; let dp = new Array ( M ) ; for ( let i = 0 ; i < M ; i ++ ) { dp [ i ] = new Array ( M ) ; for ( let j = 0 ; j < M ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = new Array ( 2 ) ; for ( let l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } } let cntR = cntNum ( str , 0 , 1 , K , 0 , 1 , dp ) ; str = ( L - 1 ) . toString ( ) ; for ( let i = 0 ; i < M ; i ++ ) { for ( let j = 0 ; j < M ; j ++ ) { for ( let k = 0 ; k < 2 ; k ++ ) for ( let l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } let cntL = cntNum ( str , 0 , 1 , K , 0 , 1 , dp ) ; return ( cntR - cntL ) ; } let L = 20 , R = 10000 , K = 14 ; document . write ( UtilCntNumRange ( L , R , K ) ) ;