Find the kth smallest number with sum of digits as m | Python3 implementation of the approach ; Recursively moving to add all the numbers upto a limit with sum of digits as m ; Max nber of digits allowed in a nber for this implementation ; Function to return the kth number with sum of digits as m ; The kth smallest number is found ; Driver code
N = 2005 NEW_LINE ans = dict ( ) NEW_LINE def dfs ( n , left , ct ) : NEW_LINE INDENT if ( ct >= 15 ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( left == 0 ) : NEW_LINE INDENT ans [ n ] = 1 NEW_LINE DEDENT for i in range ( min ( left , 9 ) + 1 ) : NEW_LINE INDENT dfs ( n * 10 + i , left - i , ct + 1 ) NEW_LINE DEDENT DEDENT def getKthNum ( m , k ) : NEW_LINE INDENT dfs ( 0 , m , 0 ) NEW_LINE c = 0 NEW_LINE for it in sorted ( ans . keys ( ) ) : NEW_LINE INDENT c += 1 NEW_LINE if ( c == k ) : NEW_LINE INDENT return it NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT m = 5 NEW_LINE k = 3 NEW_LINE print ( getKthNum ( m , k ) ) NEW_LINE