Count numbers from a given range whose product of digits is K | Java 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 ; 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
import java . util . * ; class GFG { static final int M = 100 ; static int cntNum ( String X , int i , int prod , int K , int st , int tight , int [ ] [ ] [ ] [ ] 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 ] ; } int res = 0 ; int end = tight > 0 ? X . charAt ( i ) - '0' : 9 ; for ( int 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 ) ; } } static int UtilCntNumRange ( int L , int R , int K ) { String str = String . valueOf ( R ) ; int [ ] [ ] [ ] [ ] dp = new int [ M ] [ M ] [ 2 ] [ 2 ] ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } int cntR = cntNum ( str , 0 , 1 , K , 0 , 1 , dp ) ; str = String . valueOf ( L - 1 ) ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } int cntL = cntNum ( str , 0 , 1 , K , 0 , 1 , dp ) ; return ( cntR - cntL ) ; } public static void main ( String [ ] args ) { int L = 20 , R = 10000 , K = 14 ; System . out . print ( UtilCntNumRange ( L , R , K ) ) ; } }