Count of Numbers in a Range where digit d occurs exactly K times | Python Program to find the count of numbers in a range where digit d occurs exactly K times ; states - position , count , tight , nonz ; d is required digit and K is occurrence ; This function returns the count of required numbers from 0 to num ; Last position ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; Nonz is true if we placed a non zero digit at the starting of the number ; At this position , number becomes smaller ; Next recursive call , also set nonz to 1 if current digit is non zero ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Initialize dp ; Driver Code
M = 20 NEW_LINE dp = [ ] NEW_LINE d , K = None , None NEW_LINE def count ( pos , cnt , tight , nonz , num : list ) : NEW_LINE INDENT if pos == len ( num ) : NEW_LINE INDENT if cnt == K : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if dp [ pos ] [ cnt ] [ tight ] [ nonz ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ cnt ] [ tight ] [ nonz ] NEW_LINE DEDENT ans = 0 NEW_LINE limit = 9 if tight else num [ pos ] NEW_LINE for dig in range ( limit + 1 ) : NEW_LINE INDENT currCnt = cnt NEW_LINE if dig == d : NEW_LINE INDENT if d != 0 or not d and nonz : NEW_LINE INDENT currCnt += 1 NEW_LINE DEDENT DEDENT currTight = tight NEW_LINE if dig < num [ pos ] : NEW_LINE INDENT currTight = 1 NEW_LINE DEDENT ans += count ( pos + 1 , currCnt , currTight , ( nonz or dig != 0 ) , num ) NEW_LINE DEDENT dp [ pos ] [ cnt ] [ tight ] [ nonz ] = ans NEW_LINE return dp [ pos ] [ cnt ] [ tight ] [ nonz ] NEW_LINE DEDENT def solve ( x ) : NEW_LINE INDENT global dp , K , d NEW_LINE num = [ ] NEW_LINE while x : NEW_LINE INDENT num . append ( x % 10 ) NEW_LINE x //= 10 NEW_LINE DEDENT num . reverse ( ) NEW_LINE dp = [ [ [ [ - 1 , - 1 ] for i in range ( 2 ) ] for j in range ( M ) ] for k in range ( M ) ] NEW_LINE return count ( 0 , 0 , 0 , 0 , num ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L = 11 NEW_LINE R = 100 NEW_LINE d = 2 NEW_LINE K = 1 NEW_LINE print ( solve ( R ) - solve ( L - 1 ) ) NEW_LINE DEDENT