¿Cómo encontrar el número más pequeño con la suma de dígitos dada s y el número de dígitos d ?
Ejemplos:
Input : s = 9, d = 2 Output : 18 There are many other possible numbers like 45, 54, 90, etc with sum of digits as 9 and number of digits as 2. The smallest of them is 18. Input : s = 20, d = 3 Output : 299
Una solución simple es considerar todos los números de m dígitos y realizar un seguimiento del número mínimo 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 la derecha a la izquierda (o del dígito menos significativo al más significativo).
Inicialmente deducimos 1 de la suma s para que tengamos el dígito más pequeño al final. Después de deducir 1, aplicamos un enfoque codicioso. 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. Como llenamos los dígitos de derecha a izquierda, colocamos los dígitos más altos en el lado derecho. A continuación se muestra la implementación de la idea.
C++
// C++ program to find the smallest 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 findSmallest(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 << "Smallest 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];
// deduct sum by one to account for cases later
// (There must be 1 left for the most significant
// digit)
s -= 1;
// Fill last m-1 digits (from right to left)
for (int i=m-1; i>0; i--)
{
// If sum is still greater than 9,
// digit must be 9.
if (s > 9)
{
res[i] = 9;
s -= 9;
}
else
{
res[i] = s;
s = 0;
}
}
// Whatever is left should be the most significant
// digit.
res[0] = s + 1; // The initially subtracted 1 is
// incorporated here.
cout << "Smallest number is ";
for (int i=0; i<m; i++)
cout << res[i];
}
// Driver code
int main()
{
int s = 9, m = 2;
findSmallest(m, s);
return 0;
}
Java
// Java program to find the smallest number that can be
// formed from given sum of digits and number of digits
class GFG
{
// Function to print the smallest possible number with digit sum 's'
// and 'm' number of digits
static void findSmallest(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 ? "Smallest 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];
// deduct sum by one to account for cases later
// (There must be 1 left for the most significant
// digit)
s -= 1;
// Fill last m-1 digits (from right to left)
for (int i=m-1; i>0; i--)
{
// If sum is still greater than 9,
// digit must be 9
if (s > 9)
{
res[i] = 9;
s -= 9;
}
else
{
res[i] = s;
s = 0;
}
}
// Whatever is left should be the most significant
// digit
res[0] = s + 1; // The initially subtracted 1 is
// incorporated here
System.out.print("Smallest 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;
findSmallest(m, s);
}
}
// Contributed by Pramod Kumar
Python3
# Prints the smallest possible
# number with digit sum 's'
# and 'm' number of digits.
def findSmallest(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("Smallest number is 0")
else :
print("Not possible")
return
# Sum greater than the
# maximum possible sum.
if (s > 9*m):
print("Not possible")
return
# Create an array to
# store digits of result
res=[0 for i in range(m+1)]
# deduct sum by one to
# account for cases later
# (There must be 1 left
# for the most significant
# digit)
s -= 1
# Fill last m-1 digits
# (from right to left)
for i in range(m-1,0,-1):
# If sum is still greater than 9,
# digit must be 9.
if (s > 9):
res[i] = 9
s -= 9
else:
res[i] = s
s = 0
# Whatever is left should
# be the most significant
# digit.
# The initially subtracted 1 is
# incorporated here.
res[0] = s + 1
print("Smallest number is ",end="")
for i in range(m):
print(res[i],end="")
s = 9
m = 2
findSmallest(m, s)
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find the smallest
// number that can be formed from
// given sum of digits and number
// of digits
using System;
class GFG
{
// Function to print the smallest
// possible number with digit sum 's'
// and 'm' number of digits
static void findSmallest(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 ?
"Smallest number is 0" :
"Not possible");
return ;
}
// Sum greater than the
// maximum possible sum
if (s > 9 * m)
{
Console.Write("Not possible");
return ;
}
// Create an array to
// store digits of result
int []res = new int[m];
// deduct sum by one to account
// for cases later (There must be
// 1 left for the most significant
// digit)
s -= 1;
// Fill last m-1 digits
// (from right to left)
for (int i = m - 1; i > 0; i--)
{
// If sum is still greater
// than 9, digit must be 9
if (s > 9)
{
res[i] = 9;
s -= 9;
}
else
{
res[i] = s;
s = 0;
}
}
// Whatever is left should be
// the most significant digit
// The initially subtracted 1 is
// incorporated here
res[0] = s + 1;
Console.Write("Smallest number is ");
for (int i = 0; i < m; i++)
Console.Write(res[i]);
}
// Driver Code
public static void Main ()
{
int s = 9, m = 2;
findSmallest(m, s);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the smallest
// 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 findSmallest($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 "Smallest 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 int res[m];
// deduct sum by one to account
// for cases later (There must
// be 1 left for the most
// significant digit)
$s -= 1;
// Fill last m-1 digits
// (from right to left)
for ($i = $m - 1; $i > 0; $i--)
{
// If sum is still greater
// than 9, digit must be 9.
if ($s > 9)
{
$res[$i] = 9;
$s -= 9;
}
else
{
$res[$i] = $s;
$s = 0;
}
}
// Whatever is left should be
// the most significant digit.
// The initially subtracted 1
// is incorporated here.
$res[0] = $s + 1;
echo "Smallest number is ";
for ($i = 0; $i < $m; $i++)
echo $res[$i];
}
// Driver code
$s = 9; $m = 2;
findSmallest($m, $s);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the smallest 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 findSmallest(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("Smallest 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);
// deduct sum by one to account for cases later
// (There must be 1 left for the most significant
// digit)
s -= 1;
// Fill last m-1 digits (from right to left)
for (let i=m-1; i>0; i--)
{
// If sum is still greater than 9,
// digit must be 9.
if (s > 9)
{
res[i] = 9;
s -= 9;
}
else
{
res[i] = s;
s = 0;
}
}
// Whatever is left should be the most significant
// digit.
res[0] = s + 1; // The initially subtracted 1 is
// incorporated here.
document.write("Smallest number is ");
for (let i=0; i<m; i++)
document.write(res[i]);
}
// Driver code
let s = 9, m = 2;
findSmallest(m, s);
// This code is contributed by Mayank Tyagi
</script>
Producción :
Smallest number is 18
Complejidad de tiempo: O(m), donde m representa el valor del entero dado.
Espacio auxiliar: O(m), donde m representa el valor del entero dado.
Pronto discutiremos el enfoque para encontrar el mayor número posible con la suma de dígitos y el número de dígitos dados.
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