Count of integers from the range [ 0 , N ] whose digit sum is a multiple of K | Python 3 implementation of the approach ; Function to return the count of numbers from the range [ 0 , n ] whose digit sum is a multiple of k using bottom - up dp ; The digit in this index can only be from [ 0 , num [ idx ] ] ; The digit in this index can be anything from [ 0 , 9 ] ; new_tight is the flag value for the next position ; res can 't be negative ; Function to process the string to a vector of digits from MSD to LSD ; Driver code ; For large input number n ; Total number of digits in n ; To store the states of the dp ; Process the string to a vector of digits from MSD to LSD
MAX = 10005 NEW_LINE MOD = 1000000007 NEW_LINE def countNum ( idx , sum , tight , num , len1 , k ) : NEW_LINE INDENT if ( len1 == idx ) : NEW_LINE INDENT if ( sum == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( dp [ idx ] [ sum ] [ tight ] != - 1 ) : NEW_LINE INDENT return dp [ idx ] [ sum ] [ tight ] NEW_LINE DEDENT res = 0 NEW_LINE if ( tight == 0 ) : NEW_LINE INDENT limit = num [ idx ] NEW_LINE DEDENT else : NEW_LINE INDENT limit = 9 NEW_LINE DEDENT for i in range ( limit + 1 ) : NEW_LINE INDENT new_tight = tight NEW_LINE if ( tight == 0 and i < limit ) : NEW_LINE INDENT new_tight = 1 NEW_LINE DEDENT res += countNum ( idx + 1 , ( sum + i ) % k , new_tight , num , len1 , k ) NEW_LINE res %= MOD NEW_LINE DEDENT if ( res < 0 ) : NEW_LINE INDENT res += MOD NEW_LINE DEDENT dp [ idx ] [ sum ] [ tight ] = res NEW_LINE return dp [ idx ] [ sum ] [ tight ] NEW_LINE DEDENT def process ( s ) : NEW_LINE INDENT num = [ ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT num . append ( ord ( s [ i ] ) - ord ( '0' ) ) NEW_LINE DEDENT return num NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = "98765432109876543210" NEW_LINE len1 = len ( n ) NEW_LINE k = 58 NEW_LINE dp = [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 101 ) ] for k in range ( MAX ) ] NEW_LINE num = process ( n ) NEW_LINE print ( countNum ( 0 , 0 , 0 , num , len1 , k ) ) NEW_LINE DEDENT