Dado un entero positivo N , la tarea es encontrar el número positivo más pequeño formado por dígitos distintos cuya suma de dígitos sea igual a N . Si no existe tal número, escriba “-1” .
Ejemplos:
Entrada: N = 11
Salida: 29
Explicación: La suma de los dígitos = 2 + 9 = 11 ( = N).Entrada: N = 46
Salida: -1
Enfoque: La idea se basa en las siguientes observaciones:
- Si N < 10: La respuesta requerida es N mismo.
- Si N > 45: La respuesta requerida es -1 ya que el número más pequeño que se puede formar usando dígitos no repetidos es 123456789, cuya suma de dígitos es 45.
- Caso contrario: La respuesta se puede obtener en base al siguiente patrón.
Considere los siguientes ejemplos, para entender el patrón,
Para N = 10: la salida es 19.
Para N = 11: la salida es 29.
Para N = 12: la salida es 39.
Para N = 13: la salida es 49.
…
Para N = 21: la salida es 489 Para N = 22 :
La salida es 589.
Para N = 23: La salida es 689.Al observar los resultados anteriores, es claro que la respuesta contiene dígitos en orden decreciente con una diferencia de 1 a partir del dígito de uno hasta que la suma de los dígitos es menor que N.
Siga los pasos a continuación para resolver el problema:
- Si el número dado es menor que 10, imprima el número en sí.
- Si el número dado es mayor que 45, imprima «-1» .
- De lo contrario, realice los siguientes pasos:
- Inicialice una string res para almacenar la respuesta requerida e inicialice una variable, digamos digit , como 9 .
- Iterar un bucle hasta que N ≤ dígito y realizar los siguientes pasos:
- Presione el dígito al comienzo de res .
- Decrementa N por dígito .
- Decrementa el dígito en 1 .
- Si se encuentra que el valor de N es mayor que 0 , empuje el carácter al comienzo de res .
- Después de completar los pasos anteriores, imprima el valor de res como respuesta.
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 smallest positive
// number made up of non-repeating digits
// whose sum of its digits is equal to n
void result(int n)
{
if (n > 45) {
// No such number exists
cout << -1;
return;
}
// Stores the required answer
string res;
// Store the digit at unit's place
int digit = 9;
// Iterate until n > digit
while (n > digit) {
// Push digit at the start of res
res = char('0' + digit) + res;
// Decrement n by digit
n -= digit;
// Decrement digit by 1
digit -= 1;
}
if (n > 0) {
// Push the remaining number
// as the starting digit
res = char('0' + n) + res;
}
// Print the required number
cout << res;
}
// Driver Code
int main()
{
int N = 19;
// Function Call
result(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find smallest positive
// number made up of non-repeating digits
// whose sum of its digits is equal to n
static void result(int n)
{
if (n > 45)
{
// No such number exists
System.out.print(-1);
return;
}
// Stores the required answer
String res="";
// Store the digit at unit's place
int digit = 9;
// Iterate until n > digit
while (n > digit)
{
// Push digit at the start of res
res = (char)('0' + digit) + res;
// Decrement n by digit
n -= digit;
// Decrement digit by 1
digit -= 1;
}
if (n > 0)
{
// Push the remaining number
// as the starting digit
res = (char)('0' + n) + res;
}
// Print the required number
System.out.print(res);
}
// Driver Code
public static void main(String[] args)
{
int N = 19;
// Function Call
result(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find smallest positive # number made up of non-repeating digits # whose sum of its digits is equal to n def result(n): if (n > 45): # No such number exists print(-1, end = "") return # Stores the required answer res = "" # Store the digit at unit's place digit = 9 # Iterate until n > digit while (n > digit): # Push digit at the start of res res = str(digit) + res # Decrement n by digit n -= digit # Decrement digit by 1 digit -= 1 if (n > 0): # Push the remaining number # as the starting digit res = str(n) + res # Print the required number print(res) # Driver Code if __name__ == '__main__': N = 19 # Function Call result(N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find smallest positive
// number made up of non-repeating digits
// whose sum of its digits is equal to n
static void result(int n)
{
if (n > 45)
{
// No such number exists
Console.Write(-1);
return;
}
// Stores the required answer
string res = "";
// Store the digit at unit's place
int digit = 9;
// Iterate until n > digit
while (n > digit)
{
// Push digit at the start of res
res = (char)('0' + digit) + res;
// Decrement n by digit
n -= digit;
// Decrement digit by 1
digit -= 1;
}
if (n > 0)
{
// Push the remaining number
// as the starting digit
res = (char)('0' + n) + res;
}
// Print the required number
Console.Write(res);
}
// Driver Code
public static void Main()
{
int N = 19;
// Function Call
result(N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to find smallest positive
// number made up of non-repeating digits
// whose sum of its digits is equal to n
function result(n)
{
if (n > 45) {
// No such number exists
document.write(-1);
}
// Stores the required answer
var res = "";
// Store the digit at unit's place
var digit = 9;
// Iterate until n > digit
while (n > digit) {
// Push digit at the start of res
res = String.fromCharCode(48 + digit) + res;
// Decrement n by digit
n -= digit;
// Decrement digit by 1
digit -= 1;
}
if (n > 0) {
// Push the remaining number
// as the starting digit
res = String.fromCharCode(48 + n) + res;
}
// Print the required number
document.write(res);
}
// Driver Code
var N = 19;
// Function Call
result(N);
</script>
Producción:
289
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por UnworthyProgrammer y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA