Dados dos enteros S y D , la tarea es encontrar el número que tiene D número de dígitos y la suma de sus dígitos como S tal que la diferencia entre el dígito máximo y mínimo en el número sea la mínima posible. Si son posibles varios de esos números, imprima el número más pequeño.
Ejemplos:
Entrada: S = 25, D = 4
Salida: 6667
La diferencia entre el dígito máximo 7 y el dígito mínimo 6 es 1.
Entrada: S = 27, D = 3
Salida: 999
Acercarse:
- Encontrar el número más pequeño para el número dado de dígitos y la suma ya se trata en este artículo.
- En este artículo, la idea es minimizar la diferencia entre el dígito máximo y mínimo en el número requerido. Por lo tanto, la suma s debe distribuirse uniformemente entre d dígitos.
- Si la suma se distribuye uniformemente, la diferencia puede ser como máximo 1. La diferencia es cero cuando la suma s es divisible por d. En ese caso, cada uno de los dígitos tiene el mismo valor igual a s/d.
- La diferencia es uno cuando la suma s no es divisible por d. En ese caso, después de que a cada dígito se le asigna el valor s/d, aún queda por distribuir el valor de la suma s%d.
- Como se requiere el número más pequeño, este valor restante se distribuye uniformemente entre los últimos s%d dígitos del número, es decir, los últimos s%d dígitos del número se incrementan en uno.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number having
// sum of digits as s and d number of
// digits such that the difference between
// the maximum and the minimum digit
// the minimum possible
string findNumber(int s, int d)
{
// To store the final number
string num = "";
// To store the value that is evenly
// distributed among all the digits
int val = s / d;
// To store the remaining sum that still
// remains to be distributed among d digits
int rem = s % d;
int i;
// rem stores the value that still remains
// to be distributed
// To keep the difference of digits minimum
// last rem digits are incremented by 1
for (i = 1; i <= d - rem; i++) {
num = num + to_string(val);
}
// In the last rem digits one is added to
// the value obtained by equal distribution
if (rem) {
val++;
for (i = d - rem + 1; i <= d; i++) {
num = num + to_string(val);
}
}
return num;
}
// Driver function
int main()
{
int s = 25, d = 4;
cout << findNumber(s, d);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the number having
// sum of digits as s and d number of
// digits such that the difference between
// the maximum and the minimum digit
// the minimum possible
static String findNumber(int s, int d)
{
// To store the final number
String num = "";
// To store the value that is evenly
// distributed among all the digits
int val = s / d;
// To store the remaining sum that still
// remains to be distributed among d digits
int rem = s % d;
int i;
// rem stores the value that still remains
// to be distributed
// To keep the difference of digits minimum
// last rem digits are incremented by 1
for (i = 1; i <= d - rem; i++)
{
num = num + String.valueOf(val);
}
// In the last rem digits one is added to
// the value obtained by equal distribution
if (rem > 0)
{
val++;
for (i = d - rem + 1; i <= d; i++)
{
num = num + String.valueOf(val);
}
}
return num;
}
// Driver function
public static void main(String[] args)
{
int s = 25, d = 4;
System.out.print(findNumber(s, d));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to find the number having # sum of digits as s and d number of # digits such that the difference between # the maximum and the minimum digit # the minimum possible def findNumber(s, d) : # To store the final number num = "" # To store the value that is evenly # distributed among all the digits val = s // d # To store the remaining sum that still # remains to be distributed among d digits rem = s % d # rem stores the value that still remains # to be distributed # To keep the difference of digits minimum # last rem digits are incremented by 1 for i in range(1, d - rem + 1) : num = num + str(val) # In the last rem digits one is added to # the value obtained by equal distribution if (rem) : val += 1 for i in range(d - rem + 1, d + 1) : num = num + str(val) return num # Driver function if __name__ == "__main__" : s = 25 d = 4 print(findNumber(s, d)) # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the number having
// sum of digits as s and d number of
// digits such that the difference between
// the maximum and the minimum digit
// the minimum possible
static String findNumber(int s, int d)
{
// To store the readonly number
String num = "";
// To store the value that is evenly
// distributed among all the digits
int val = s / d;
// To store the remaining sum that still
// remains to be distributed among d digits
int rem = s % d;
int i;
// rem stores the value that still remains
// to be distributed
// To keep the difference of digits minimum
// last rem digits are incremented by 1
for (i = 1; i <= d - rem; i++)
{
num = num + String.Join("", val);
}
// In the last rem digits one is added to
// the value obtained by equal distribution
if (rem > 0)
{
val++;
for (i = d - rem + 1; i <= d; i++)
{
num = num + String.Join("", val);
}
}
return num;
}
// Driver function
public static void Main(String[] args)
{
int s = 25, d = 4;
Console.Write(findNumber(s, d));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to find the number having
// sum of digits as s and d number of
// digits such that the difference between
// the maximum and the minimum digit
// the minimum possible
function findNumber(s, d)
{
// To store the final number
var num = [] ;
// To store the value that is evenly
// distributed among all the digits
var val = parseInt(s / d);
// To store the remaining sum that still
// remains to be distributed among d digits
var rem = s % d;
// rem stores the value that still remains
// to be distributed
// To keep the difference of digits minimum
// last rem digits are incremented by 1
for (var i = 1; i <= d - rem; i++)
{
// num = num.concat(toString(val));
num.push(val.toString());
}
// In the last rem digits one is added to
// the value obtained by equal distribution
if (rem != 0)
{
val++;
for (var i = d - rem + 1; i <= d; i++)
{
// num = num + toString(val);
num.push(val.toString());
}
}
return num;
}
var s = 25, d = 4;
var n=findNumber(s, d);
for(var i = 0; i < n.length; i++)
{
document.write(n[i]);
}
// This code is contributed by SoumikMondal
</script>
Producción:
6667
Complejidad temporal: O(d)
Espacio auxiliar: O(1)