Count numbers with exactly K non | To store digits of N ; visited map ; DP Table ; Push all the digits of N into digits vector ; Function returns the count ; If desired number is formed whose sum is odd ; If it is not present in map , mark it as true and return 1 ; Sum is present in map already ; Desired result not found ; If that state is already calculated just return that state value ; Upper limit ; To store the count of desired numbers ; If k is non - zero , i ranges from 0 to j else [ 1 , j ] ; If current digit is 0 , decrement k and recurse sum is not changed as we are just adding 0 that makes no difference ; If i is non zero , then k remains unchanged and value is added to sum ; Memoize and return ; Driver code ; K is the number of exact non - zero elements to have in number ; break N into its digits ; We keep record of 0 s we need to place in the number
digits = [ ] NEW_LINE vis = [ False for i in range ( 170 ) ] NEW_LINE dp = [ [ [ [ 0 for l in range ( 170 ) ] for k in range ( 2 ) ] for j in range ( 19 ) ] for i in range ( 19 ) ] NEW_LINE def ConvertIntoDigit ( n ) : NEW_LINE INDENT while ( n > 0 ) : NEW_LINE INDENT dig = n % 10 ; NEW_LINE digits . append ( dig ) ; NEW_LINE n //= 10 ; NEW_LINE DEDENT digits . reverse ( ) NEW_LINE DEDENT def solve ( idx , k , tight , sum ) : NEW_LINE INDENT if ( idx == len ( digits ) and k == 0 and sum % 2 == 1 ) : NEW_LINE INDENT if ( not vis [ sum ] ) : NEW_LINE INDENT vis [ sum ] = True ; NEW_LINE return 1 ; NEW_LINE DEDENT return 0 ; NEW_LINE DEDENT if ( idx > len ( digits ) ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ idx ] [ k ] [ tight ] [ sum ] ) : NEW_LINE INDENT return dp [ idx ] [ k ] [ tight ] [ sum ] ; NEW_LINE DEDENT j = 0 ; NEW_LINE if ( idx < len ( digits ) and tight == 0 ) : NEW_LINE INDENT j = digits [ idx ] ; NEW_LINE DEDENT else : NEW_LINE INDENT j = 9 ; NEW_LINE DEDENT cnt = 0 ; NEW_LINE for i in range ( 0 if k else 1 , j + 1 ) : NEW_LINE INDENT newtight = tight ; NEW_LINE if ( i < j ) : NEW_LINE INDENT newtight = 1 ; NEW_LINE DEDENT if ( i == 0 ) : NEW_LINE INDENT cnt += solve ( idx + 1 , k - 1 , newtight , sum ) ; NEW_LINE DEDENT else : NEW_LINE INDENT cnt += solve ( idx + 1 , k , newtight , sum + i ) ; NEW_LINE DEDENT DEDENT dp [ idx ] [ k ] [ tight ] [ sum ] = cnt NEW_LINE return cnt ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 169 NEW_LINE k = 2 ; NEW_LINE ConvertIntoDigit ( N ) ; NEW_LINE k = len ( digits ) - k ; NEW_LINE print ( solve ( 0 , k , 0 , 0 ) ) NEW_LINE DEDENT