#practicelinkdiv {display: nessuno! importante; }Dato un numero intero S E D L'attività è quella di trovare il numero più grande con data somma delle cifre S e il numero di cifre D .
Esempi:
Pratica consigliata Numero maggiore possibile Provalo!Ingresso: s = 9 d = 2
Produzione: 90Ingresso: s = 20 d = 3
Produzione: 992
Approccio ingenuo:
Considera tutto M numeri di cifre e mantieni un file max variabile per archiviare il numero massimo con M cifre e la somma delle cifre come S .
Complessità temporale: O (10M).
Spazio ausiliario: O (1)
Trova il numero più grande con il numero dato di cifre e la somma delle cifre Approccio avido
Di seguito è riportata l'idea di risolvere il problema:
L'idea è di uno per uno riempire tutte le cifre da più a sinistra a destra confronta il Somma rimanente con 9 se la somma rimanente è superiore o uguale a 9 9 nella posizione corrente, inserisci la somma rimanente. Poiché le cifre vengono riempite da sinistra a destra, le cifre più alte verranno posizionate sul lato sinistro, quindi ottenere il numero più grande E .
Illustrazione:

Segui i passaggi seguenti per implementare l'idea:
- Se S è zero
- Se m = 1 stampa 0
- Altrimenti non è possibile tali numeri.
- Se s> 9*m, non è possibile tale numero.
- Esegui un giro per loop da 0 a M-1
- Se S> = 9 Sottrai 9 da S e stampa 9.
- Altrimenti stampare s e impostare s su 0 .
Di seguito è riportato l'implementazione dell'approccio sopra:
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>
Produzione
Largest number is 90
Complessità temporale di questa soluzione è O (M).
Spazio ausiliario: O (m) dove m è l'intero dato.
Approccio: algoritmo avido
- Crea una stringa vuota per archiviare il risultato
- Se D è 1 append S al risultato e restituirlo
- Loop dalla cifra più a sinistra alla cifra più a destra
UN. Se la somma rimanente delle cifre è maggiore o uguale a 9 APPEND 9 al risultato e sottrarre 9 dalla somma rimanente delle cifre
B. Se la somma rimanente delle cifre è inferiore a 9 aggiungono la somma rimanente delle cifre al risultato e riempi le cifre rimanenti con 0s - Restituire il risultato
#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
Produzione
90 992
Complessità temporale: O (d)
Spazio ausiliario: O (d)