Count of Numbers in Range where the number does not contain more than K non zero digits | This function returns the count of required numbers from 0 to num ; Last position ; If count of non zero digits is less than or equal to K ; 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 ] ; If the current digit is nonzero increment currCnt ; At this position , number becomes smaller ; Next recursive call ; This function converts a number into its digit vector and uses above function to compute the answer ; Initialize dp ; Driver Code ; states - position , count , tight ; K is the number of non zero digits
def countInRangeUtil ( pos , cnt , tight , num ) : 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 ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ cnt ] [ tight ] 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 != 0 : NEW_LINE INDENT currCnt += 1 NEW_LINE DEDENT currTight = tight NEW_LINE if dig < num [ pos ] : NEW_LINE INDENT currTight = 1 NEW_LINE DEDENT ans += countInRangeUtil ( pos + 1 , currCnt , currTight , num ) NEW_LINE DEDENT dp [ pos ] [ cnt ] [ tight ] = ans NEW_LINE return dp [ pos ] [ cnt ] [ tight ] NEW_LINE DEDENT def countInRange ( x ) : NEW_LINE INDENT global dp , K , M 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 ( M ) ] for j in range ( M ) ] NEW_LINE return countInRangeUtil ( 0 , 0 , 0 , num ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT dp = [ ] NEW_LINE M = 20 NEW_LINE K = 0 NEW_LINE L = 1 NEW_LINE R = 1000 NEW_LINE K = 3 NEW_LINE print ( countInRange ( R ) - countInRange ( L - 1 ) ) NEW_LINE L = 9995 NEW_LINE R = 10005 NEW_LINE K = 2 NEW_LINE print ( countInRange ( R ) - countInRange ( L - 1 ) ) NEW_LINE DEDENT