Smallest number with given sum of digits and sum of square of digits
Given the sum of digits a and sum of the square of digits b . Find the smallest number with the given sum of digits and the sum of the square of digits. The number should not contain more than 100 digits. Print -1 if no such number exists or if the number of digits is more than 100.
Examples:
Input : a = 18, b = 162
Output : 99
Explanation : 99 is the smallest possible number whose sum of digits = 9 + 9 = 18 and sum of squares of digits is 92+92 = 162.
Input : a = 12, b = 9
Output : -1
Approach:
Since the smallest number can be of 100 digits, it cannot be stored. Hence the first step to solve it will be to find the minimum number of digits which can give us the sum of digits as and sum of the square of digits as . To find the minimum number of digits, we can use Dynamic Programming. DP[a][b] signifies the minimum number of digits in a number whose sum of the digits will be and sum of the square of digits will be . If there does not exist any such number then DP[a][b] will be -1.
Since the number cannot exceed 100 digits, DP array will be of size 101*8101. Iterate for every digit, and try all possible combination of digits which gives us the sum of digits as and sum of the square of digits as . Store the minimum number of digits in DP[a][b] using the below recurrence relation:
DP[a][b] = min( minimumNumberOfDigits(a – i, b – (i * i)) + 1 )
where 1<=i<=9
After getting the minimum number of digits, find the digits. To find the digits, check for all combinations and print those digits which satisfies the condition below:
1 + dp[a – i][b – i * i] == dp[a][b]
where 1<=i<=9
If the condition above is met by any of i, reduce a by i and b by i*i and break. Keep on repeating the above process to find all the digits till a is 0 and b is 0.
Below is the implementation of the above approach:
C++
// CPP program to find the Smallest number with given sum of // digits and sum of square of digits #include <bits/stdc++.h> using namespace std; int dp[901][8101]; // Top down dp to find minimum number of digits with given // sum of digits a and sum of square of digits as b int minimumNumberOfDigits( int a, int b) { // Invalid condition if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; // Number of digits satisfied if (a == 0 && b == 0) return 0; // Memoization if (dp[a][b] != -1) return dp[a][b]; // Initialize ans as maximum as we have to find the // minimum number of digits int ans = 101; // Check for all possible combinations of digits for ( int i = 9; i >= 1; i--) { // recurrence call int k = minimumNumberOfDigits(a - i, b - (i * i)); // If the combination of digits cannot give sum as a // and sum of square of digits as b if (k != -1) ans = min(ans, k + 1); } // Returns the minimum number of digits return dp[a][b] = ans; } // Function to print the digits that gives // sum as a and sum of square of digits as b void printSmallestNumber( int a, int b) { // initialize the dp array as -1 memset (dp, -1, sizeof (dp)); // base condition dp[0][0] = 0; // function call to get the minimum number of digits int k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == -1 || k > 100) cout << "-1" ; else { // Printing the digits from the most significant // digit while (a > 0 && b > 0) { // Trying all combinations for ( int i = 1; i <= 9; i++) { // checking conditions for minimum digits if (a >= i && b >= i * i && 1 + dp[a - i][b - i * i] == dp[a][b]) { cout << i; a -= i; b -= i * i; break ; } } } } } // Driver Code int main() { int a = 18, b = 162; // Function call to print the smallest number printSmallestNumber(a, b); } |
C
// C program to find the Smallest number with given sum of // digits and sum of square of digits #include <stdio.h> #include <string.h> // Find minimum between two numbers. int min( int num1, int num2) { return (num1 > num2) ? num2 : num1; } int dp[901][8101]; // Top down dp to find minimum number of digits with given // sum of digits a and sum of square of digits as b int minimumNumberOfDigits( int a, int b) { // Invalid condition if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; // Number of digits satisfied if (a == 0 && b == 0) return 0; // Memoization if (dp[a][b] != -1) return dp[a][b]; // Initialize ans as maximum as we have to find the // minimum number of digits int ans = 101; // Check for all possible combinations of digits for ( int i = 9; i >= 1; i--) { // recurrence call int k = minimumNumberOfDigits(a - i, b - (i * i)); // If the combination of digits cannot give sum as a // and sum of square of digits as b if (k != -1) ans = min(ans, k + 1); } // Returns the minimum number of digits return dp[a][b] = ans; } // Function to print the digits that gives // sum as a and sum of square of digits as b void printSmallestNumber( int a, int b) { // initialize the dp array as -1 memset (dp, -1, sizeof (dp)); // base condition dp[0][0] = 0; // function call to get the minimum number of digits int k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == -1 || k > 100) printf ( "-1" ); else { // Printing the digits from the most significant // digit while (a > 0 && b > 0) { // Trying all combinations for ( int i = 1; i <= 9; i++) { // checking conditions for minimum digits if (a >= i && b >= i * i && 1 + dp[a - i][b - i * i] == dp[a][b]) { printf ( "%d" , i); a -= i; b -= i * i; break ; } } } } } // Driver Code int main() { int a = 18, b = 162; // Function call to print the smallest number printSmallestNumber(a, b); } // This code is contributed by Sania Kumari Gupta |
Java
import java.util.Arrays; // Java program to find the Smallest number // with given sum of digits and // sum of square of digits class GFG { static int dp[][] = new int [ 901 ][ 8101 ]; // Top down dp to find minimum number of digits with // given sum of digits a and sum of square of digits as b static int minimumNumberOfDigits( int a, int b) { // Invalid condition if (a > b || a < 0 || b < 0 || a > 900 || b > 8100 ) { return - 1 ; } // Number of digits satisfied if (a == 0 && b == 0 ) { return 0 ; } // Memoization if (dp[a][b] != - 1 ) { return dp[a][b]; } // Initialize ans as maximum as we have to find the // minimum number of digits int ans = 101 ; // Check for all possible combinations of digits for ( int i = 9 ; i >= 1 ; i--) { // recurrence call int k = minimumNumberOfDigits(a - i, b - (i * i)); // If the combination of digits cannot give sum as a // and sum of square of digits as b if (k != - 1 ) { ans = Math.min(ans, k + 1 ); } } // Returns the minimum number of digits return dp[a][b] = ans; } // Function to print the digits that gives // sum as a and sum of square of digits as b static void printSmallestNumber( int a, int b) { // initialize the dp array as -1 for ( int [] row : dp) { Arrays.fill(row, - 1 ); } // base condition dp[ 0 ][ 0 ] = 0 ; // function call to get the minimum number of digits int k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == - 1 || k > 100 ) { System.out.println( "-1" ); } else { // Printing the digits from the most significant digit while (a > 0 && b > 0 ) { // Trying all combinations for ( int i = 1 ; i <= 9 ; i++) { // checking conditions for minimum digits 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 ; } } } } } // Driver Code public static void main(String args[]) { int a = 18 , b = 162 ; // Function call to print the smallest number printSmallestNumber(a, b); } } // This code is contributed by PrinciRaj19992 |
Python3
# Python3 program to find the Smallest number # with given sum of digits and # sum of square of digits dp = [[ - 1 for i in range ( 8101 )] for i in range ( 901 )] # Top down dp to find minimum number of digits with # given sum of digits a and sum of square of digits as b def minimumNumberOfDigits(a,b): # Invalid condition if (a > b or a < 0 or b < 0 or a > 900 or b > 8100 ): return - 1 # Number of digits satisfied if (a = = 0 and b = = 0 ): return 0 # Memoization if (dp[a][b] ! = - 1 ): return dp[a][b] # Initialize ans as maximum as we have to find the # minimum number of digits ans = 101 #Check for all possible combinations of digits for i in range ( 9 , 0 , - 1 ): # recurrence call k = minimumNumberOfDigits(a - i, b - (i * i)) # If the combination of digits cannot give sum as a # and sum of square of digits as b if (k ! = - 1 ): ans = min (ans, k + 1 ) # Returns the minimum number of digits dp[a][b] = ans return ans # Function to print the digits that gives # sum as a and sum of square of digits as b def printSmallestNumber(a,b): # initialize the dp array as for i in range ( 901 ): for j in range ( 8101 ): dp[i][j] = - 1 # base condition dp[ 0 ][ 0 ] = 0 # function call to get the minimum number of digits k = minimumNumberOfDigits(a, b) # When there does not exists any number if (k = = - 1 or k > 100 ): print ( - 1 ,end = '') else : # Printing the digits from the most significant digit while (a > 0 and b > 0 ): # Trying all combinations for i in range ( 1 , 10 ): #checking conditions for minimum digits if (a > = i and b > = i * i and 1 + dp[a - i][b - i * i] = = dp[a][b]): print (i,end = '') a - = i b - = i * i break # Driver Code if __name__ = = '__main__' : a = 18 b = 162 # Function call to print the smallest number printSmallestNumber(a,b) # This code is contributed by sahilshelangia |
C#
// C# program to find the Smallest number // with given sum of digits and // sum of square of digits using System; public class GFG { static int [,]dp = new int [901,8101]; // Top down dp to find minimum number of digits with // given sum of digits a and sum of square of digits as b static int minimumNumberOfDigits( int a, int b) { // Invalid condition if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) { return -1; } // Number of digits satisfied if (a == 0 && b == 0) { return 0; } // Memoization if (dp[a,b] != -1) { return dp[a,b]; } // Initialize ans as maximum as we have to find the // minimum number of digits int ans = 101; // Check for all possible combinations of digits for ( int i = 9; i >= 1; i--) { // recurrence call int k = minimumNumberOfDigits(a - i, b - (i * i)); // If the combination of digits cannot give sum as a // and sum of square of digits as b if (k != -1) { ans = Math.Min(ans, k + 1); } } // Returns the minimum number of digits return dp[a,b] = ans; } // Function to print the digits that gives // sum as a and sum of square of digits as b static void printSmallestNumber( int a, int b) { // initialize the dp array as -1 for ( int i = 0; i < dp.GetLength(0); i++) for ( int j = 0; j < dp.GetLength(1); j++) dp[i, j] = -1; // base condition dp[0,0] = 0; // function call to get the minimum number of digits int k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == -1 || k > 100) { Console.WriteLine( "-1" ); } else { // Printing the digits from the most significant digit while (a > 0 && b > 0) { // Trying all combinations for ( int i = 1; i <= 9; i++) { // checking conditions for minimum digits if (a >= i && b >= i * i && 1 + dp[a - i,b - i * i] == dp[a,b]) { Console.Write(i); a -= i; b -= i * i; break ; } } } } } // Driver Code public static void Main() { int a = 18, b = 162; // Function call to print the smallest number printSmallestNumber(a, b); } } // This code is contributed by PrinciRaj19992 |
Javascript
<script> // JavaScript program to find the Smallest number // with given sum of digits and // sum of square of digits // initialize the dp array as -1 dp = new Array(901).fill(-1).map(() => new Array(8101).fill(-1));; // Top down dp to find minimum // number of digits with // given sum of digits a and // sum of square of digits as b function minimumNumberOfDigits(a, b) { // Invalid condition if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; // Number of digits satisfied if (a == 0 && b == 0) return 0; // Memoization if (dp[a][b] != -1) return dp[a][b]; // Initialize ans as maximum as we have to find the // minimum number of digits var ans = 101; // Check for all possible combinations of digits for ( var i = 9; i >= 1; i--) { // recurrence call var k = minimumNumberOfDigits(a - i, b - (i * i)); // If the combination of digits cannot give sum as a // and sum of square of digits as b if (k != -1) ans = Math.min(ans, k + 1); } // Returns the minimum number of digits return dp[a][b] = ans; } // Function to print the digits that gives // sum as a and sum of square of digits as b function printSmallestNumber(a, b) { // base condition dp[0][0] = 0; // function call to get the // minimum number of digits var k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == -1 || k > 100) document.write( "-1" ); else { // Printing the digits from the // most significant digit while (a > 0 && b > 0) { // Trying all combinations for ( var i = 1; i <= 9; i++) { // checking conditions for minimum digits if (a >= i && b >= i * i && 1 + dp[a - i][b - i * i] == dp[a][b]) { document.write( i); a -= i; b -= i * i; break ; } } } } } var a = 18, b = 162; // Function call to print the smallest number printSmallestNumber(a,b); // This code is contributed by SoumikMondal </script> |
Output
99
Time Complexity : O(900*8100*9)
Auxiliary Space : O(900*8100)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
// C++ code for the above approach #include <cstring> #include <iostream> using namespace std; int dp[901][8101]; // function to find minimum number of digits with given // sum of digits a and sum of square of digits as b int minimumNumberOfDigits( int a, int b) { // base case if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; if (a == 0 && b == 0) return 0; // initialize Dp with -1 memset (dp, -1, sizeof (dp)); // Base Case dp[0][0] = 0; // iterating over subproblems to get the current // solution of dp from previous computations for ( int i = 0; i <= a; i++) { for ( int j = 0; j <= b; j++) { if (dp[i][j] == -1) continue ; for ( int digit = 1; digit <= 9; digit++) { if (i + digit <= a && j + digit * digit <= b) { int new_a = i + digit; int new_b = j + digit * digit; if (dp[new_a][new_b] == -1 || dp[new_a][new_b] > dp[i][j] + 1) dp[new_a][new_b] = dp[i][j] + 1; } } } } // return answer return dp[a][b]; } // Function to print the digits that gives // sum as a and sum of square of digits as b void printSmallestNumber( int a, int b) { int k = minimumNumberOfDigits(a, b); // When there does not exists any number if (k == -1 || k > 100) cout << "-1" ; else { // Printing the digits from the most significant // digit while (a > 0 && b > 0) { // Trying all combinations for ( int digit = 1; digit <= 9; digit++) { // checking conditions for minimum digits if (a >= digit && b >= digit * digit && dp[a][b] == dp[a - digit] [b - digit * digit] + 1) { cout << digit; a -= digit; b -= digit * digit; break ; } } } } } // Driver Code int main() { int a = 18, b = 162; printSmallestNumber(a, b); return 0; } |
Java
import java.util.Arrays; public class Main { static int [][] dp = new int [ 901 ][ 8101 ]; // Function to find minimum number of digits with given // sum of digits a and sum of square of digits as b static int minimumNumberOfDigits( int a, int b) { // Base case if (a > b || a < 0 || b < 0 || a > 900 || b > 8100 ) return - 1 ; if (a == 0 && b == 0 ) return 0 ; // Initialize dp with -1 for ( int i = 0 ; i <= 900 ; i++) { Arrays.fill(dp[i], - 1 ); } // Base Case dp[ 0 ][ 0 ] = 0 ; // Iterating over subproblems to get the current // solution of dp from previous computations for ( int i = 0 ; i <= a; i++) { for ( int j = 0 ; j <= b; j++) { if (dp[i][j] == - 1 ) continue ; for ( int digit = 1 ; digit <= 9 ; digit++) { if (i + digit <= a && j + digit * digit <= b) { int new_a = i + digit; int new_b = j + digit * digit; if (dp[new_a][new_b] == - 1 || dp[new_a][new_b] > dp[i][j] + 1 ) dp[new_a][new_b] = dp[i][j] + 1 ; } } } } // Return the answer return dp[a][b]; } // Function to print the digits that give // sum as a and sum of square of digits as b static void printSmallestNumber( int a, int b) { int k = minimumNumberOfDigits(a, b); // When there does not exist any number if (k == - 1 || k > 100 ) System.out.print( "-1" ); else { // Printing the digits from the most significant // digit while (a > 0 && b > 0 ) { // Trying all combinations for ( int digit = 1 ; digit <= 9 ; digit++) { // Checking conditions for minimum // digits if (a >= digit && b >= digit * digit && dp[a][b] == dp[a - digit] [b - digit * digit] + 1 ) { System.out.print(digit); a -= digit; b -= digit * digit; break ; } } } } } // Driver Code public static void main(String[] args) { int a = 18 , b = 162 ; printSmallestNumber(a, b); } } |
Python3
# Python code for the above approach # Function to find minimum number of digits with given # sum of digits a and sum of square of digits as b def minimumNumberOfDigits(a, b): # base case if a > b or a < 0 or b < 0 or a > 900 or b > 8100 : return - 1 if a = = 0 and b = = 0 : return 0 # initialize dp with -1 dp = [[ - 1 for _ in range ( 8101 )] for _ in range ( 901 )] # Base Case dp[ 0 ][ 0 ] = 0 # iterating over subproblems to get the current # solution of dp from previous computations for i in range (a + 1 ): for j in range (b + 1 ): if dp[i][j] = = - 1 : continue for digit in range ( 1 , 10 ): if i + digit < = a and j + digit * digit < = b: new_a = i + digit new_b = j + digit * digit if dp[new_a][new_b] = = - 1 or dp[new_a][new_b] > dp[i][j] + 1 : dp[new_a][new_b] = dp[i][j] + 1 # return answer return dp # Function to print the digits that gives # sum as a and sum of square of digits as b def printSmallestNumber(a, b, dp): k = dp[a][b] # When there does not exist any number if k = = - 1 or k > 100 : print ( "-1" ) else : # Printing the digits from the most significant # digit while a > 0 and b > 0 : # Trying all combinations for digit in range ( 1 , 10 ): # checking conditions for minimum digits if a > = digit and b > = digit * digit and dp[a][b] = = dp[a - digit][b - digit * digit] + 1 : print (digit, end = "") a - = digit b - = digit * digit break # Driver Code if __name__ = = "__main__" : a = 18 b = 162 dp = minimumNumberOfDigits(a, b) printSmallestNumber(a, b, dp) # This code is contributed by Susobhan Akhuli |
C#
using System; class Program { static int [, ] dp = new int [901, 8101]; // Function to find the minimum number of digits with a // given sum of digits a and sum of squares of digits as // b static int MinimumNumberOfDigits( int a, int b) { // Base case if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; if (a == 0 && b == 0) return 0; // Initialize dp with -1 for ( int i = 0; i < 901; i++) { for ( int j = 0; j < 8101; j++) { dp[i, j] = -1; } } // Base Case dp[0, 0] = 0; // Iterating over subproblems to get the current // solution of dp from previous computations for ( int i = 0; i <= a; i++) { for ( int j = 0; j <= b; j++) { if (dp[i, j] == -1) continue ; for ( int digit = 1; digit <= 9; digit++) { if (i + digit <= a && j + digit * digit <= b) { int newA = i + digit; int newB = j + digit * digit; if (dp[newA, newB] == -1 || dp[newA, newB] > dp[i, j] + 1) dp[newA, newB] = dp[i, j] + 1; } } } } // Return the answer return dp[a, b]; } // Function to print the digits that give a sum as a and // sum of the square of digits as b static void PrintSmallestNumber( int a, int b) { int k = MinimumNumberOfDigits(a, b); // When there does not exist any number if (k == -1 || k > 100) { Console.WriteLine( "-1" ); } else { // Printing the digits from the most significant // digit while (a > 0 && b > 0) { // Trying all combinations for ( int digit = 1; digit <= 9; digit++) { // Checking conditions for the minimum // digits if (a >= digit && b >= digit * digit && dp[a, b] == dp[a - digit, b - digit * digit] + 1) { Console.Write(digit); a -= digit; b -= digit * digit; break ; } } } } } static void Main( string [] args) { int a = 18, b = 162; PrintSmallestNumber(a, b); } } |
Javascript
// Javascript code of the above Approach let dp = new Array(901); for (let i = 0; i <= 900; i++) { dp[i] = new Array(8101).fill(-1); } function minimumNumberOfDigits(a, b) { if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) return -1; if (a === 0 && b === 0) return 0; // Base Case dp[0][0] = 0; // Iterating over subproblems to get the current // solution of dp from previous computations for (let i = 0; i <= a; i++) { for (let j = 0; j <= b; j++) { if (dp[i][j] === -1) continue ; for (let digit = 1; digit <= 9; digit++) { if (i + digit <= a && j + digit * digit <= b) { let new_a = i + digit; let new_b = j + digit * digit; if (dp[new_a][new_b] === -1 || dp[new_a][new_b] > dp[i][j] + 1) dp[new_a][new_b] = dp[i][j] + 1; } } } } // Return answer return dp[a][b]; } function printSmallestNumber(a, b) { let k = minimumNumberOfDigits(a, b); let result = '' ; if (k === -1 || k > 100) { console.log( "-1" ); } else { while (a > 0 && b > 0) { for (let digit = 1; digit <= 9; digit++) { if (a >= digit && b >= digit * digit && dp[a][b] === dp[a - digit][b - digit * digit] + 1) { result += digit; a -= digit; b -= digit * digit; break ; } } } console.log(result); } } // Driver Code const a = 18; const b = 162; printSmallestNumber(a, b); |
Output
99
Time Complexity : O(900*8100*9)
Auxiliary Space : O(900*8100)