human
Write me a code to count of Numbers in Range where the number does not contain more than K non zero digits and the other steps required given the following:
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"
How can the above be solved in Python?
assistant
#Here is code to count of Numbers in Range where the number does not contain more than K non zero digits and the other steps required.
 def countInRangeUtil ( pos , cnt , tight , num ) :
	if pos == len ( num ) :
		if cnt <= K :
			return 1
		return 0
	if dp [ pos ] [ cnt ] [ tight ] != - 1 :
		return dp [ pos ] [ cnt ] [ tight ]
	ans = 0
	limit = 9 if tight else num [ pos ]
	for dig in range ( limit + 1 ) :
		currCnt = cnt
		if dig != 0 :
			currCnt += 1
		currTight = tight
		if dig < num [ pos ] :
			currTight = 1
		ans += countInRangeUtil ( pos + 1 , currCnt , currTight , num )
	dp [ pos ] [ cnt ] [ tight ] = ans
	return dp [ pos ] [ cnt ] [ tight ]
def countInRange ( x ) :
	global dp , K , M
	num = [ ]
	while x :
		num . append ( x % 10 )
		x //= 10
	num . reverse ( )
	dp = [ [ [ - 1 , - 1 ] for i in range ( M ) ] for j in range ( M ) ]
	return countInRangeUtil ( 0 , 0 , 0 , num )
if __name__ == " _ _ main _ _ " :
	dp = [ ]
	M = 20
	K = 0
	L = 1
	R = 1000
	K = 3
	print ( countInRange ( R ) - countInRange ( L - 1 ) )
	L = 9995
	R = 10005
	K = 2
	print ( countInRange ( R ) - countInRange ( L - 1 ) )