Găsiți cel mai mare număr cu numărul dat de cifre și suma cifrelor
Încercați -l în practica GFG 
#practicelinkdiv {display: none! Important; }
Ieșire
Ieșire
#practicelinkdiv {display: none! Important; } Dat un număr întreg s şi D. Sarcina este de a găsi cel mai mare număr cu suma de cifră dată s și numărul de cifre D. .
Exemple:
Practică recomandată Cel mai mare număr posibil Încearcă!Intrare: s = 9 d = 2
Ieșire: 90Intrare: s = 20 d = 3
Ieșire: 992
Abordare naivă:
Luați în considerare pe toate m numerele cifrelor și păstrați un Max variabilă pentru a stoca numărul maxim cu m cifre și sumă de cifră ca s .
Complexitate a timpului: O (10 m )
Spațiu auxiliar: O (1)
Găsiți cel mai mare număr cu numărul dat de cifre și suma cifrelor Abordare lacomă
Mai jos este ideea de a rezolva problema:
Ideea este ca unul câte unul să completeze toate cifrele de la stânga cel mai dreapta compară suma rămasă cu 9 dacă suma rămasă este mai mare sau egală cu 9 9 la poziția actuală, altfel puneți suma rămasă. Deoarece cifrele sunt umplute de la stânga la dreapta, cele mai mari cifre vor fi plasate pe partea stângă, deci obțineți cel mai mare număr şi .
Ilustrare:
Urmați pașii de mai jos pentru a implementa ideea:
- Dacă S este zero
- Dacă m = 1 tipărire 0
- Altfel nu este posibil un astfel de număr.
- Dacă s> 9*m, atunci nu este posibil un astfel de număr.
- Rulați o buclă de la 0 până la M-1
- Dacă s> = 9 scade 9 din S și imprimați 9.
- Altfel tipăriți și set s la 0 .
Mai jos este implementarea abordării de mai sus:
C++ // C++ program to find the largest number that can be // formed from given sum of digits and number of digits. #include using namespace std ; // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. void findLargest ( int m int s ) { // If sum of digits is 0 then a number is possible // only if number of digits is 1. if ( s == 0 ) { ( m == 1 ) ? cout < < 'Largest number is ' < < 0 : cout < < 'Not possible' ; return ; } // Sum greater than the maximum possible sum. if ( s > 9 * m ) { cout < < 'Not possible' ; return ; } // Create an array to store digits of result int res [ m ]; // Fill from most significant digit to least // significant digit. for ( int i = 0 ; i < m ; i ++ ) { // Fill 9 first to make the number largest if ( s >= 9 ) { res [ i ] = 9 ; s -= 9 ; } // If remaining sum becomes less than 9 then // fill the remaining sum else { res [ i ] = s ; s = 0 ; } } cout < < 'Largest number is ' ; for ( int i = 0 ; i < m ; i ++ ) cout < < res [ i ]; } // Driver code int main () { int s = 9 m = 2 ; findLargest ( m s ); return 0 ; }
C // C program to find the largest number that can be // formed from given sum of digits and number of digits. #include // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. void findLargest ( int m int s ) { // If sum of digits is 0 then a number is possible // only if number of digits is 1. if ( s == 0 ) { ( m == 1 ) ? printf ( 'Largest number is 0' ) : printf ( 'Not possible' ); return ; } // Sum greater than the maximum possible sum. if ( s > 9 * m ) { printf ( 'Not possible' ); return ; } // Create an array to store digits of result int res [ m ]; // Fill from most significant digit to least // significant digit. for ( int i = 0 ; i < m ; i ++ ) { // Fill 9 first to make the number largest if ( s >= 9 ) { res [ i ] = 9 ; s -= 9 ; } // If remaining sum becomes less than 9 then // fill the remaining sum else { res [ i ] = s ; s = 0 ; } } printf ( 'Largest number is ' ); for ( int i = 0 ; i < m ; i ++ ) printf ( '%d' res [ i ]); } // Driver code int main () { int s = 9 m = 2 ; findLargest ( m s ); return 0 ; } // This code is contributed by Sania Kumari Gupta
Java // Java program to find the largest number that can be // formed from given sum of digits and number of digits class GFG { // Function to print the largest possible number with digit sum 's' // and 'm' number of digits static void findLargest ( int m int s ) { // If sum of digits is 0 then a number is possible // only if number of digits is 1 if ( s == 0 ) { System . out . print ( m == 1 ? 'Largest number is 0' : 'Not possible' ); return ; } // Sum greater than the maximum possible sum if ( s > 9 * m ) { System . out . println ( 'Not possible' ); return ; } // Create an array to store digits of result int [] res = new int [ m ] ; // Fill from most significant digit to least // significant digit for ( int i = 0 ; i < m ; i ++ ) { // Fill 9 first to make the number largest if ( s >= 9 ) { res [ i ] = 9 ; s -= 9 ; } // If remaining sum becomes less than 9 then // fill the remaining sum else { res [ i ] = s ; s = 0 ; } } System . out . print ( 'Largest number is ' ); for ( int i = 0 ; i < m ; i ++ ) System . out . print ( res [ i ] ); } // driver program public static void main ( String [] args ) { int s = 9 m = 2 ; findLargest ( m s ); } } // Contributed by Pramod Kumar
Python3 # Python 3 program to find # the largest number that # can be formed from given # sum of digits and number # of digits. # Prints the smallest # possible number with digit # sum 's' and 'm' number of # digits. def findLargest ( m s ) : # If sum of digits is 0 # then a number is possible # only if number of digits # is 1. if ( s == 0 ) : if ( m == 1 ) : print ( 'Largest number is ' '0' end = '' ) else : print ( 'Not possible' end = '' ) return # Sum greater than the # maximum possible sum. if ( s > 9 * m ) : print ( 'Not possible' end = '' ) return # Create an array to # store digits of # result res = [ 0 ] * m # Fill from most significant # digit to least significant # digit. for i in range ( 0 m ) : # Fill 9 first to make # the number largest if ( s >= 9 ) : res [ i ] = 9 s = s - 9 # If remaining sum # becomes less than # 9 then fill the # remaining sum else : res [ i ] = s s = 0 print ( 'Largest number is ' end = '' ) for i in range ( 0 m ) : print ( res [ i ] end = '' ) # Driver code s = 9 m = 2 findLargest ( m s ) # This code is contributed by Nikita Tiwari.
C# // C# program to find the // largest number that can // be formed from given sum // of digits and number of digits using System ; class GFG { // Function to print the // largest possible number // with digit sum 's' and // 'm' number of digits static void findLargest ( int m int s ) { // If sum of digits is 0 // then a number is possible // only if number of digits is 1 if ( s == 0 ) { Console . Write ( m == 1 ? 'Largest number is 0' : 'Not possible' ); return ; } // Sum greater than the // maximum possible sum if ( s > 9 * m ) { Console . WriteLine ( 'Not possible' ); return ; } // Create an array to // store digits of result int [] res = new int [ m ]; // Fill from most significant // digit to least significant digit for ( int i = 0 ; i < m ; i ++ ) { // Fill 9 first to make // the number largest if ( s >= 9 ) { res [ i ] = 9 ; s -= 9 ; } // If remaining sum becomes // less than 9 then // fill the remaining sum else { res [ i ] = s ; s = 0 ; } } Console . Write ( 'Largest number is ' ); for ( int i = 0 ; i < m ; i ++ ) Console . Write ( res [ i ]); } // Driver Code static public void Main () { int s = 9 m = 2 ; findLargest ( m s ); } } // This code is Contributed by ajit
PHP // PHP program to find the largest // number that can be formed from // given sum of digits and number // of digits. // Prints the smallest possible // number with digit sum 's' // and 'm' number of digits. function findLargest ( $m $s ) { // If sum of digits is 0 then // a number is possible only if // number of digits is 1. if ( $s == 0 ) { if (( $m == 1 ) == true ) echo 'Largest number is ' 0 ; else echo 'Not possible' ; return ; } // Sum greater than the // maximum possible sum. if ( $s > 9 * $m ) { echo 'Not possible' ; return ; } // Create an array to store // digits of result Fill from // most significant digit to // least significant digit. for ( $i = 0 ; $i < $m ; $i ++ ) { // Fill 9 first to make // the number largest if ( $s >= 9 ) { $res [ $i ] = 9 ; $s -= 9 ; } // If remaining sum becomes // less than 9 then fill // the remaining sum else { $res [ $i ] = $s ; $s = 0 ; } } echo 'Largest number is ' ; for ( $i = 0 ; $i < $m ; $i ++ ) echo $res [ $i ]; } // Driver code $s = 9 ; $m = 2 ; findLargest ( $m $s ); // This code is contributed by m_kit ?>
JavaScript < script > // Javascript program to find the largest number that can be // formed from given sum of digits and number of digits. // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. function findLargest ( m s ) { // If sum of digits is 0 then a number is possible // only if number of digits is 1. if ( s == 0 ) { ( m == 1 ) ? document . write ( 'Largest number is ' + 0 ) : document . write ( 'Not possible' ); return ; } // Sum greater than the maximum possible sum. if ( s > 9 * m ) { document . write ( 'Not possible' ); return ; } // Create an array to store digits of result let res = new Array ( m ); // Fill from most significant digit to least // significant digit. for ( let i = 0 ; i < m ; i ++ ) { // Fill 9 first to make the number largest if ( s >= 9 ) { res [ i ] = 9 ; s -= 9 ; } // If remaining sum becomes less than 9 then // fill the remaining sum else { res [ i ] = s ; s = 0 ; } } document . write ( 'Largest number is ' ); for ( let i = 0 ; i < m ; i ++ ) document . write ( res [ i ]); } // Driver code let s = 9 m = 2 ; findLargest ( m s ); // This code is contributed by Mayank Tyagi < /script>
Ieșire
Largest number is 90
Complexitatea timpului a acestei soluții este O (M).
Spațiu auxiliar: O (m) unde m este numărul întreg dat.
Abordare: Algoritmul lacom
- Creați un șir gol pentru a stoca rezultatul
- Dacă D este 1 anexă la rezultat și returnează -l
- Buclă de la cea mai stângă cifră la cea mai dreaptă cifră
o. Dacă suma rămasă de cifre este mai mare sau egală cu 9 anexa 9 la rezultatul și scade 9 din suma rămasă de cifre
b. Dacă suma rămasă de cifre este mai mică de 9, adăugați suma rămasă de cifre la rezultat și completați cifrele rămase cu 0s - Returnează rezultatul
#include #include using namespace std ; int largest_number ( int s int d ) { if ( s == 0 ) { return 0 ; } if ( s > 9 * d ) { return -1 ; } string result = '' ; for ( int i = 0 ; i < d ; i ++ ) { if ( s >= 9 ) { result += '9' ; s -= 9 ; } else { result += to_string ( s ); s = 0 ; } if ( s == 0 && i < d -1 ) { result += string ( d - i -1 '0' ); break ; } } return stoi ( result ); } int main () { // Test case 1 cout < < largest_number ( 9 2 ) < < endl ; // Output: 90 // Test case 2 cout < < largest_number ( 20 3 ) < < endl ; // Output: 992 return 0 ; }
Java import java.util.* ; public class Main { public static int largest_number ( int s int d ) { // If s is 0 then the largest number is 0. if ( s == 0 ) { return 0 ; } // If s is greater than 9 times d then it is // impossible to form a d-digit number whose sum of // digits is s. if ( s > 9 * d ) { return - 1 ; } // Initialize an empty string to store the result. String result = '' ; // Loop through each digit of the number. for ( int i = 0 ; i < d ; i ++ ) { // If s is greater than or equal to 9 then add // 9 to the result and subtract 9 from s. if ( s >= 9 ) { result += '9' ; s -= 9 ; } // Otherwise add s to the result and set s to // 0. else { result += Integer . toString ( s ); s = 0 ; } // If s is 0 and there are still digits left to // fill then fill the remaining digits with 0s // and break out of the loop. if ( s == 0 && i < d - 1 ) { result += String . join ( '' Collections . nCopies ( d - i - 1 '0' )); break ; } } // Convert the result to an integer and return it. return Integer . parseInt ( result ); } public static void main ( String [] args ) { // Test case 1 System . out . println ( largest_number ( 9 2 )); // Output: 90 // Test case 2 System . out . println ( largest_number ( 20 3 )); // Output: 992 } }
Python3 def largest_number ( s d ): if s == 0 : return 0 if s > 9 * d : return - 1 result = '' for i in range ( d ): if s >= 9 : result += '9' s -= 9 else : result += str ( s ) s = 0 if s == 0 and i < d - 1 : result += '0' * ( d - i - 1 ) break return int ( result ) # Test case 1 print ( largest_number ( 9 2 )) # Output: 90 # Test case 2 print ( largest_number ( 20 3 )) # Output: 992
C# using System ; class Program { static int LargestNumber ( int s int d ) { if ( s == 0 ) { return 0 ; } if ( s > 9 * d ) { return - 1 ; } string result = '' ; for ( int i = 0 ; i < d ; i ++ ) { if ( s >= 9 ) { result += '9' ; s -= 9 ; } else { result += s . ToString (); s = 0 ; } if ( s == 0 && i < d - 1 ) { result += new string ( '0' d - i - 1 ); break ; } } return int . Parse ( result ); } static void Main ( string [] args ) { // Test case 1 Console . WriteLine ( LargestNumber ( 9 2 )); // Output: 90 // Test case 2 Console . WriteLine ( LargestNumber ( 20 3 )); // Output: 992 } }
JavaScript function largestNumber ( s d ) { if ( s == 0 ) { return 0 ; } if ( s > 9 * d ) { return - 1 ; } let result = '' ; for ( let i = 0 ; i < d ; i ++ ) { if ( s >= 9 ) { result += '9' ; s -= 9 ; } else { result += s . toString (); s = 0 ; } if ( s == 0 && i < d - 1 ) { result += '0' . repeat ( d - i - 1 ); break ; } } return parseInt ( result ); } // Test cases console . log ( largestNumber ( 9 2 )); // Output: 90 console . log ( largestNumber ( 20 3 )); // Output: 992
Ieșire
90 992
Complexitate a timpului: O (D)
Spațiu auxiliar: O (D)
