Count numbers from a given range whose product of digits is K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  100 NEW_LINE int cntNum ( string X , int i , int prod , int K , int st , int tight , int dp [ M ] [ M ] [ 2 ] [ 2 ] ) { if ( i >= X . length ( ) prod > K ) { return prod == K ; } if ( dp [ prod ] [ i ] [ tight ] [ st ] != -1 ) { return dp [ prod ] [ i ] [ tight ] [ st ] ; } int res = 0 ; int end = tight ? X [ i ] - '0' : 9 ; for ( int j = 0 ; j <= end ; j ++ ) { if ( j == 0 && ! st ) { res += cntNum ( X , i + 1 , prod , K , false , ( tight & ( j == end ) ) , dp ) ; } else { res += cntNum ( X , i + 1 , prod * j , K , true , ( tight & ( j == end ) ) , dp ) ; } return dp [ prod ] [ i ] [ tight ] [ st ] = res ; } int UtilCntNumRange ( int L , int R , int K ) { string str = to_string ( R ) ; int dp [ M ] [ M ] [ 2 ] [ 2 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; int cntR = cntNum ( str , 0 , 1 , K , false , true , dp ) ; str = to_string ( L - 1 ) ; memset ( dp , -1 , sizeof ( dp ) ) ; int cntL = cntNum ( str , 0 , 1 , K , false , true , dp ) ; return ( cntR - cntL ) ; } int main ( ) { int L = 20 , R = 10000 , K = 14 ; cout << UtilCntNumRange ( L , R , K ) ; }