Count numbers less than N containing digits from the given set : Digit DP | Java 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 ; Initially no subproblem is solved till now ; 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 java . util . * ; class GFG { static int [ ] [ ] dp = new int [ 15 ] [ 2 ] ; static String convertToString ( int num ) { return String . valueOf ( num ) ; } static int calculate ( int pos , int tight , int D [ ] , int sz , String num ) { if ( pos == num . length ( ) ) return 1 ; if ( dp [ pos ] [ tight ] != - 1 ) return dp [ pos ] [ tight ] ; int val = 0 ; if ( tight == 0 ) { for ( int i = 0 ; i < sz ; i ++ ) { if ( D [ i ] < ( num . charAt ( pos ) - '0' ) ) { val += calculate ( pos + 1 , 1 , D , sz , num ) ; } else if ( D [ i ] == num . charAt ( pos ) - '0' ) val += calculate ( pos + 1 , tight , D , sz , num ) ; } } else { for ( int i = 0 ; i < sz ; i ++ ) { val += calculate ( pos + 1 , tight , D , sz , num ) ; } } return dp [ pos ] [ tight ] = val ; } static int countNumbers ( int D [ ] , int N , int sz ) { String num = convertToString ( N ) ; int len = num . length ( ) ; for ( int i = 0 ; i < 15 ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) dp [ i ] [ j ] = - 1 ; int ans = calculate ( 0 , 0 , D , sz , num ) ; for ( int i = 1 ; i < len ; i ++ ) ans += calculate ( i , 1 , D , sz , num ) ; return ans ; } public static void main ( String [ ] args ) { int sz = 3 ; int D [ ] = { 1 , 4 , 9 } ; int N = 10 ; System . out . print ( countNumbers ( D , N , sz ) ) ; } }