Smallest number with given sum of digits and sum of square of digits | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 901 ] [ 8101 ] ; 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 = min ( ans , k + 1 ) ; } return dp [ a ] [ b ] = ans ; } void printSmallestNumber ( int a , int b ) { memset ( dp , -1 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = 0 ; int k = minimumNumberOfDigits ( a , b ) ; if ( k == -1 k > 100 ) cout << " - 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 ] ) { cout << i ; a -= i ; b -= i * i ; break ; } } } } } int main ( ) { int a = 18 , b = 162 ; printSmallestNumber ( a , b ) ; }