Count of numbers from range [ L , R ] whose sum of digits is Y | Set 2 | Python program for the above approach ; Function to find the sum of digits of numbers in the range [ 0 , X ] ; Check if count of digits in a number greater than count of digits in X ; Check if sum of digits of a number is equal to Y ; Check if current subproblem has already been comrputed ; Stores count of numbers whose sum of digits is Y ; Check if the number exceeds Y or not ; Iterate over all possible values of i - th digits ; Update res ; Return res ; Utility function to count the numbers in the range [ L , R ] whose sum of digits is Y ; Base Case ; Stores numbers in the form of its equivalent ; Stores overlapping subproblems ; Stores count of numbers in the range [ 0 , R ] ; Update str ; Stores count of numbers in the range [ 0 , L - 1 ] ; Driver Code
M = 1000 NEW_LINE def cntNum ( X , i , sum , tight , dp ) : NEW_LINE INDENT if ( i >= len ( X ) or sum < 0 ) : NEW_LINE INDENT if ( sum == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if ( dp [ sum ] [ i ] [ tight ] != - 1 ) : NEW_LINE INDENT return dp [ sum ] [ i ] [ tight ] NEW_LINE DEDENT res , end = 0 , 9 NEW_LINE if tight : NEW_LINE INDENT end = ord ( X [ i ] ) - ord ( '0' ) NEW_LINE DEDENT for j in range ( end + 1 ) : NEW_LINE INDENT res += cntNum ( X , i + 1 , sum - j , ( tight & ( j == end ) ) , dp ) NEW_LINE DEDENT dp [ sum ] [ i ] [ tight ] = res NEW_LINE return res NEW_LINE DEDENT def UtilCntNumRange ( L , R , Y ) : NEW_LINE INDENT if ( R == 0 and Y == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT strr = str ( R ) NEW_LINE dp = [ [ [ - 1 for i in range ( 2 ) ] for i in range ( M ) ] for i in range ( M ) ] NEW_LINE cntR = cntNum ( strr , 0 , Y , True , dp ) NEW_LINE strr = str ( L - 1 ) NEW_LINE cntL = cntNum ( strr , 0 , Y , True , dp ) NEW_LINE return ( cntR - cntL ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L , R , Y = 20 , 10000 , 14 NEW_LINE print ( UtilCntNumRange ( L , R , Y ) ) NEW_LINE DEDENT