Número positivo más pequeño formado por dígitos no repetidos cuya suma de dígitos es N

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:
    • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *