Count numbers ( smaller than or equal to N ) with given digit sum | N can be max 10 ^ 18 and hence digitsum will be 162 maximum . ; If sum_so_far equals to given sum then return 1 else 0 ; Our constructed number should not become greater than N . ; If tight is true then it will also be true for ( i + 1 ) digit . ; Driver code
def solve ( i , tight , sum_so_far , Sum , number , length ) : NEW_LINE INDENT if i == length : NEW_LINE INDENT if sum_so_far == Sum : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT ans = dp [ i ] [ tight ] [ sum_so_far ] NEW_LINE if ans != - 1 : NEW_LINE INDENT return ans NEW_LINE DEDENT ans = 0 NEW_LINE for currdigit in range ( 0 , 10 ) : NEW_LINE INDENT currdigitstr = str ( currdigit ) NEW_LINE if not tight and currdigitstr > number [ i ] : NEW_LINE INDENT break NEW_LINE DEDENT ntight = tight or currdigitstr < number [ i ] NEW_LINE nsum_so_far = sum_so_far + currdigit NEW_LINE ans += solve ( i + 1 , ntight , nsum_so_far , Sum , number , length ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT count , Sum = 0 , 4 NEW_LINE number = "100" NEW_LINE dp = [ [ [ - 1 for i in range ( 162 ) ] for j in range ( 2 ) ] for k in range ( 18 ) ] NEW_LINE print ( solve ( 0 , 0 , 0 , Sum , number , len ( number ) ) ) NEW_LINE DEDENT