¿Cómo encontrar el número más grande con la suma de dígitos dada s y el número de dígitos d ?
Ejemplos:
Input : s = 9, d = 2 Output : 90 Input : s = 20, d = 3 Output : 992
Una solución simple es considerar todos los números de m dígitos y realizar un seguimiento del número máximo con suma de dígitos como s. Un límite superior cercano a la complejidad temporal de esta solución es O(10 m ).
Hay un enfoque Greedy para resolver el problema. La idea es llenar uno por uno todos los dígitos de izquierda a derecha (o del dígito más significativo al menos significativo).
Comparamos la suma restante con 9 si la suma restante es mayor que 9, ponemos 9 en la posición actual, de lo contrario ponemos la suma restante. Dado que llenamos los dígitos de izquierda a derecha, colocamos los dígitos más altos en el lado izquierdo, por lo tanto, obtenemos el número más grande.
La siguiente imagen es una ilustración del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the largest number that can be // formed from given sum of digits and number of digits. #include <iostream> 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 <stdio.h> // 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 // 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>
Producción :
Largest number is 90
La complejidad temporal de esta solución es O(m).
Espacio Auxiliar : O(m), donde m es el entero dado.
Este artículo es una contribución de Vaibhav Agarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA