Smallest number with given sum of digits and sum of square of digits | Python3 program to find the Smallest number with given sum of digits and sum of square of digits ; Top down dp to find minimum number of digits with given sum of dits a and sum of square of digits as b ; Invalid condition ; Number of digits satisfied ; Memoization ; Initialize ans as maximum as we have to find the minimum number of digits ; Check for all possible combinations of digits ; recurrence call ; If the combination of digits cannot give sum as a and sum of square of digits as b ; Returns the minimum number of digits ; Function to print the digits that gives sum as a and sum of square of digits as b ; initialize the dp array as ; base condition ; function call to get the minimum number of digits ; When there does not exists any number ; Printing the digits from the most significant digit ; Trying all combinations ; checking conditions for minimum digits ; Driver Code ; Function call to print the smallest number
dp = [ [ - 1 for i in range ( 8101 ) ] for i in range ( 901 ) ] NEW_LINE def minimumNumberOfDigits ( a , b ) : NEW_LINE INDENT if ( a > b or a < 0 or b < 0 or a > 900 or b > 8100 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( a == 0 and b == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ a ] [ b ] != - 1 ) : NEW_LINE INDENT return dp [ a ] [ b ] NEW_LINE DEDENT ans = 101 NEW_LINE for i in range ( 9 , 0 , - 1 ) : NEW_LINE INDENT k = minimumNumberOfDigits ( a - i , b - ( i * i ) ) NEW_LINE if ( k != - 1 ) : NEW_LINE INDENT ans = min ( ans , k + 1 ) NEW_LINE DEDENT DEDENT dp [ a ] [ b ] = ans NEW_LINE return ans NEW_LINE DEDENT def printSmallestNumber ( a , b ) : NEW_LINE INDENT for i in range ( 901 ) : NEW_LINE INDENT for j in range ( 8101 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT dp [ 0 ] [ 0 ] = 0 NEW_LINE k = minimumNumberOfDigits ( a , b ) NEW_LINE if ( k == - 1 or k > 100 ) : NEW_LINE INDENT print ( - 1 , end = ' ' ) NEW_LINE DEDENT else : NEW_LINE INDENT while ( a > 0 and b > 0 ) : NEW_LINE INDENT for i in range ( 1 , 10 ) : NEW_LINE INDENT if ( a >= i and b >= i * i and 1 + dp [ a - i ] [ b - i * i ] == dp [ a ] [ b ] ) : NEW_LINE INDENT print ( i , end = ' ' ) NEW_LINE a -= i NEW_LINE b -= i * i NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = 18 NEW_LINE b = 162 NEW_LINE printSmallestNumber ( a , b ) NEW_LINE DEDENT