¿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