Encuentre el número más grande con el número de dígitos y la suma de dígitos dados

¿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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *