Smallest number with given sum of digits and sum of square of digits | Java 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 - 1 ; 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
import java . util . Arrays ; class GFG { static int dp [ ] [ ] = new int [ 901 ] [ 8101 ] ; static int minimumNumberOfDigits ( int a , int b ) { if ( a > b a < 0 b < 0 a > 900 b > 8100 ) { return - 1 ; } if ( a == 0 && b == 0 ) { return 0 ; } if ( dp [ a ] [ b ] != - 1 ) { return dp [ a ] [ b ] ; } int ans = 101 ; for ( int i = 9 ; i >= 1 ; i -- ) { int k = minimumNumberOfDigits ( a - i , b - ( i * i ) ) ; if ( k != - 1 ) { ans = Math . min ( ans , k + 1 ) ; } } return dp [ a ] [ b ] = ans ; } static void printSmallestNumber ( int a , int b ) { for ( int [ ] row : dp ) { Arrays . fill ( row , - 1 ) ; } dp [ 0 ] [ 0 ] = 0 ; int k = minimumNumberOfDigits ( a , b ) ; if ( k == - 1 k > 100 ) { System . out . println ( " - 1" ) ; } else { while ( a > 0 && b > 0 ) { for ( int i = 1 ; i <= 9 ; i ++ ) { if ( a >= i && b >= i * i && 1 + dp [ a - i ] [ b - i * i ] == dp [ a ] [ b ] ) { System . out . print ( i ) ; a -= i ; b -= i * i ; break ; } } } } } public static void main ( String args [ ] ) { int a = 18 , b = 162 ; printSmallestNumber ( a , b ) ; } }