Raskite didžiausią skaičių su nurodytu skaitmenų skaičiumi ir skaitmenų suma
Išbandykite tai GFG praktikoje 
#practicelinkdiv {ekranas: nėra! SVARBU; }
Išvestis
Išvestis
#practicelinkdiv {ekranas: nėra! SVARBU; } Duotas sveikasis skaičius s ir d Užduotis yra rasti didžiausią skaičių su nurodyta skaitmenų suma s ir skaitmenų skaičius d .
Pavyzdžiai:
Rekomenduojama praktika Didžiausias skaičius įmanomas Išbandykite!Įvestis: S = 9 D = 2
Išvestis: 90Įvestis: S = 20 D = 3
Išvestis: 992
Naivus požiūris:
Apsvarstykite viską m skaitmenų numeriai ir saugokite a Maks Kintamasis, kad būtų galima laikyti maksimalų skaičių su m skaitmenys ir skaitmenų suma kaip s .
Laiko sudėtingumas: O (10 m ).
Pagalbinė erdvė: O (1)
Raskite didžiausią skaičių su nurodytu skaitmenų skaičiumi ir skaitmenų suma Godus požiūris
Žemiau yra idėja išspręsti problemą:
Idėja yra viena po vieno užpildykite visus skaitmenis nuo kairės iki dešinės, palyginti likusi suma Su 9, jei likusi suma yra didesnė arba lygi 9 9, esant dabartinei padėtyje, likusia suma. Kadangi skaitmenys užpildomi iš kairės į dešinę, didžiausi skaitmenys bus dedami į kairę pusę, todėl gaukite didžiausią skaičių ir .
Iliustracija:
Atlikite žemiau pateiktus veiksmus, kad įgyvendintumėte idėją:
- Jei S yra nulis
- Jei m = 1 spausdinti 0
- Kitu atveju tokio skaičiaus neįmanoma.
- Jei s> 9*m, tokio skaičiaus neįmanoma.
- Paleiskite kilpą iš Nuo 0 iki M-1
- Jei s> = 9 atimkite 9 iš S ir spausdinkite 9.
- Else spausdinti ir nustatyti S į 0 .
Žemiau yra aukščiau pateikto požiūrio įgyvendinimas:
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>
Išvestis
Largest number is 90
Laiko sudėtingumas šio sprendimo yra O (M).
Pagalbinė erdvė: O (m), kur M yra nurodytas sveikasis skaičius.
Požiūris: godus algoritmas
- Sukurkite tuščią eilutę, kad būtų galima išsaugoti rezultatą
- Jei d yra 1 pridedamas prie rezultato ir grąžinkite jį
- Kilpa iš kairės skaitmens iki dešiniojo skaitmens
a. Jei likusi skaitmenų suma yra didesnė arba lygi 9 priedui iki rezultato ir atimkite 9 iš likusių skaitmenų sumos
b. Jei likusi skaitmenų suma yra mažesnė nei 9, pridėkite likusią skaitmenų sumą iki rezultato ir užpildykite likusius skaitmenis 0S - Grąžinkite rezultatą
#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
Išvestis
90 992
Laiko sudėtingumas: O (d)
Pagalbinė erdvė: O (d)
