Count of integers of length N and value less than K such that they contain digits only from the given set | Python3 implementation of the approach ; Function to convert a number into vector ; Push all the digits of N from the end one by one to the vector ; If the original number was 0 ; Reverse the vector elements ; Return the required vector ; Function to return the count of B length integers which are less than C and they contain digits from set A [ ] only ; Convert number to digit array ; Case 1 : No such number possible as the generated numbers will always be greater than C ; Case 2 : All integers of length B are valid as they all are less than C ; contain 0 ; Case 3 ; Update the lower [ ] array such that lower [ i ] stores the count of elements in A [ ] which are less than i ; For first index we can 't use 0 ; Whether ( i - 1 ) digit of generated number can be equal to ( i - 1 ) digit of C ; Is digit [ i - 1 ] present in A ? ; Driver code
MAX = 10 NEW_LINE def numToVec ( N ) : NEW_LINE INDENT digit = [ ] NEW_LINE while ( N != 0 ) : NEW_LINE INDENT digit . append ( N % 10 ) NEW_LINE N = N // 10 NEW_LINE DEDENT if ( len ( digit ) == 0 ) : NEW_LINE INDENT digit . append ( 0 ) NEW_LINE DEDENT digit = digit [ : : - 1 ] NEW_LINE return digit NEW_LINE DEDENT def solve ( A , B , C ) : NEW_LINE INDENT d , d2 = 0 , 0 NEW_LINE digit = numToVec ( C ) NEW_LINE d = len ( A ) NEW_LINE if ( B > len ( digit ) or d == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( B < len ( digit ) ) : NEW_LINE INDENT if ( A [ 0 ] == 0 and B != 1 ) : NEW_LINE INDENT return ( d - 1 ) * pow ( d , B - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return pow ( d , B ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp = [ 0 for i in range ( B + 1 ) ] NEW_LINE lower = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE for i in range ( d ) : NEW_LINE INDENT lower [ A [ i ] + 1 ] = 1 NEW_LINE DEDENT for i in range ( 1 , MAX + 1 ) : NEW_LINE INDENT lower [ i ] = lower [ i - 1 ] + lower [ i ] NEW_LINE DEDENT flag = True NEW_LINE dp [ 0 ] = 0 NEW_LINE for i in range ( 1 , B + 1 ) : NEW_LINE INDENT d2 = lower [ digit [ i - 1 ] ] NEW_LINE dp [ i ] = dp [ i - 1 ] * d NEW_LINE if ( i == 1 and A [ 0 ] == 0 and B != 1 ) : NEW_LINE INDENT d2 = d2 - 1 NEW_LINE DEDENT if ( flag ) : NEW_LINE INDENT dp [ i ] += d2 NEW_LINE DEDENT flag = ( flag & ( lower [ digit [ i - 1 ] + 1 ] == lower [ digit [ i - 1 ] ] + 1 ) ) NEW_LINE DEDENT return dp [ B ] NEW_LINE DEDENT DEDENT A = [ 0 , 1 , 2 , 5 ] NEW_LINE N = 2 NEW_LINE k = 21 NEW_LINE print ( solve ( A , N , k ) ) NEW_LINE