Dados dos enteros positivos N y K , la tarea es encontrar el número más pequeño cuya suma de dígitos sea N y cada dígito distinto en ese número ocurra como máximo K veces. Si no existe tal número, escriba “-1” .
Ejemplos:
Entrada: N = 25, K = 3
Salida: 799
Explicación: Suma de dígitos del número = (7 + 9 + 9) = 25 y es la menor posible.Entrada: N =100, K = 2
Salida: -1
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos para resolver el problema:
- La suma máxima posible de dígitos de cualquier número que tenga cada dígito como máximo K veces es K * 45 .
- Inicialice una string, digamos res , para almacenar la string resultante formada.
- Si N es mayor que K * 45 , no se puede obtener dicho número. Por lo tanto, imprima “-1” .
- De lo contrario, siga restando cada número a partir de 9 a 1 , de N , como máximo K veces. Agregue el dígito actual a res . Continúe hasta que N sea menor que el dígito actual.
- Si N es más pequeño que el dígito actual, inserte N como un dígito para res .
- Después de completar los pasos anteriores, imprima la string res en el orden inverso como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest number
// whose sum of digits is N and each
// digit occurring at most K times
void findSmallestNumberPossible(int N, int K)
{
// Maximum sum possible using
// each digit at most K times
if (N > 45 * K) {
cout << "-1";
return;
}
// Append smallest number into
// the resultant string
string res = "";
int count = 0;
// Iterate over the range [9, 1]
for (int i = 9; i >= 1;) {
// If the count of the digit
// is K, then update count and
// check for the next digit
if (count == K) {
i--;
count = 0;
}
// If N is greater than
// current digit
if (N > i) {
// Subtract i from N
N -= i;
// Insert i as a digit
res += (char)48 + i;
}
else {
// Insert remaining N
// as a digit
res += (char)N + 48;
N = 0;
break;
}
// Increment count
count++;
}
// Reverse the string
reverse(res.begin(),
res.end());
// Print the answer
cout << res;
}
// Driver Code
int main()
{
int N = 25, K = 3;
// Function Call
findSmallestNumberPossible(N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the smallest number
// whose sum of digits is N and each
// digit occurring at most K times
static void findSmallestNumberPossible(int N, int K)
{
// Maximum sum possible using
// each digit at most K times
if (N > 45 * K)
{
System.out.print("-1");
return;
}
// Append smallest number into
// the resultant string
StringBuilder res = new StringBuilder();
int count = 0;
// Iterate over the range [9, 1]
for(int i = 9; i >= 1😉
{
// If the count of the digit
// is K, then update count and
// check for the next digit
if (count == K)
{
i--;
count = 0;
}
// If N is greater than
// current digit
if (N > i)
{
// Subtract i from N
N -= i;
// Insert i as a digit
res.append((char)('0' + i));
}
else
{
// Insert remaining N
// as a digit
res.append((char)('0' + N));
N = 0;
break;
}
// Increment count
count++;
}
// Reverse the string
res.reverse();
// Print the answer
System.out.print(res.toString());
}
// Driver Code
public static void main(String[] args)
{
int N = 25, K = 3;
// Function Call
findSmallestNumberPossible(N, K);
}
}
// This code is contributed by jithin
Python3
# Python3 program for the above approach
# Function to find the smallest number
# whose sum of digits is N and each
# digit occurring at most K times
def findSmallestNumberPossible(N, K) :
# Maximum sum possible using
# each digit at most K times
if (N > 45 * K) :
print("-1", endl = "");
return;
# Append smallest number into
# the resultant string
res = "";
count = 0;
# Iterate over the range [9, 1]
i = 9;
while i >= 1 :
# If the count of the digit
# is K, then update count and
# check for the next digit
if (count == K) :
i -= 1;
count = 0;
# If N is greater than
# current digit
if (N > i) :
# Subtract i from N
N -= i;
# Insert i as a digit
res += chr(48 + i);
else :
# Insert remaining N
# as a digit
res += chr(N + 48);
N = 0;
break;
# Increment count
count += 1;
# Reverse the string
res = res[::-1]
# Print the answer
print(res, end = "");
# Driver Code
if __name__ == "__main__" :
N = 25; K = 3;
# Function Call
findSmallestNumberPossible(N, K);
# This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the smallest number
// whose sum of digits is N and each
// digit occurring at most K times
static void findSmallestNumberPossible(int N, int K)
{
// Maximum sum possible using
// each digit at most K times
if (N > 45 * K)
{
Console.Write("-1");
return;
}
// Append smallest number into
// the resultant string
string res = "" ;
int count = 0;
// Iterate over the range [9, 1]
for (int i = 9; i >= 1;)
{
// If the count of the digit
// is K, then update count and
// check for the next digit
if (count == K)
{
i--;
count = 0;
}
// If N is greater than
// current digit
if (N > i)
{
// Subtract i from N
N -= i;
// Insert i as a digit
res += (char)('0' + i);
}
else
{
// Insert remaining N
// as a digit
res += (char)('0' + N);
N = 0;
break;
}
// Increment count
count++;
}
// Reverse the string
string ans = "";
for (int i = res.Length - 1; i >= 0; i--)
{
ans += res[i] + "";
}
// Print the answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
int N = 25, K = 3;
// Function Call
findSmallestNumberPossible(N, K);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the smallest number
// whose sum of digits is N and each
// digit occurring at most K times
function findSmallestNumberPossible(N, K) {
// Maximum sum possible using
// each digit at most K times
if (N > 45 * K) {
document.write("-1");
return;
}
// Append smallest number into
// the resultant string
var res = "";
var count = 0;
// Iterate over the range [9, 1]
for (var i = 9; i >= 1; ) {
// If the count of the digit
// is K, then update count and
// check for the next digit
if (count === K) {
i--;
count = 0;
}
// If N is greater than
// current digit
if (N > i) {
// Subtract i from N
N -= i;
// Insert i as a digit
res += String.fromCharCode("0".charCodeAt(0) + i);
} else {
// Insert remaining N
// as a digit
res += String.fromCharCode("0".charCodeAt(0) + N);
N = 0;
break;
}
// Increment count
count++;
}
// Reverse the string
var ans = "";
for (var i = res.length - 1; i >= 0; i--) {
ans += res[i] + "";
}
// Print the answer
document.write(ans);
}
// Driver Code
var N = 25,
K = 3;
// Function Call
findSmallestNumberPossible(N, K);
</script>
Producción:
799
Complejidad de tiempo: O(log 10 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA