Count of numbers between range having only non | Function to return the count of required numbers from 0 to num ; Last position ; 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 zero and nonz is 1 , we can 't place it ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Initialize dp ; Driver code ; n is the sum of digits and number should be divisible by m ; States - position , sum , rem , tight sum can have values upto 162 , if we are dealing with numbers upto 10 ^ 18 when all 18 digits are 9 , then sum is 18 * 9 = 162
def count ( pos , Sum , rem , tight , nonz , num ) : NEW_LINE INDENT if pos == len ( num ) : NEW_LINE INDENT if rem == 0 and Sum == n : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if dp [ pos ] [ Sum ] [ rem ] [ tight ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ Sum ] [ rem ] [ tight ] NEW_LINE DEDENT ans = 0 NEW_LINE if tight : NEW_LINE INDENT limit = 9 NEW_LINE DEDENT else : NEW_LINE INDENT limit = num [ pos ] NEW_LINE DEDENT for d in range ( 0 , limit + 1 ) : NEW_LINE INDENT if d == 0 and nonz : NEW_LINE INDENT continue NEW_LINE DEDENT currSum = Sum + d NEW_LINE currRem = ( rem * 10 + d ) % m NEW_LINE currF = int ( tight or ( d < num [ pos ] ) ) NEW_LINE ans += count ( pos + 1 , currSum , currRem , currF , nonz or d , num ) NEW_LINE DEDENT dp [ pos ] [ Sum ] [ rem ] [ tight ] = ans NEW_LINE return ans NEW_LINE DEDENT def solve ( x ) : NEW_LINE INDENT num = [ ] NEW_LINE global dp NEW_LINE while x > 0 : 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 ( 165 ) ] for k in range ( M ) ] NEW_LINE return count ( 0 , 0 , 0 , 0 , 0 , num ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L , R = 1 , 100 NEW_LINE n , m , M = 8 , 2 , 20 NEW_LINE dp = [ ] NEW_LINE print ( solve ( R ) - solve ( L ) ) NEW_LINE DEDENT