Dado un entero positivo N , la tarea es encontrar el número positivo más grande formado por dígitos distintos que tengan la suma de sus dígitos igual a N . Si no existe tal número, escriba “-1” .
Ejemplos:
Entrada: N = 25
Salida: 98710
Explicación:
El número 98710 es el número más grande que contiene solo dígitos únicos y la suma de sus dígitos (9 + 8 + 7 + 1 + 0) es N (= 25).Entrada: N = 50
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si el valor de N es al menos 45: El resultado requerido es -1 ya que el número más grande que se puede formar usando dígitos no repetidos es 9876543210 , cuya suma de dígitos es 45 .
- Para todos los demás valores de N: Para obtener el número más grande, comience con el dígito más grande, es decir, 9 , y siga reduciéndolo y sumándolo al número requerido. El número requerido debe contener un 0 al final, ya que aumenta el valor sin cambiar la suma de los dígitos.
Siga los pasos a continuación para resolver el problema:
- Si el número dado N es mayor que 45 , imprima «-1» .
- De lo contrario, realice los siguientes pasos:
- Inicialice una variable, digamos num como 0 para almacenar el resultado requerido, y una variable, digamos digit , como 9 .
- Iterar un bucle hasta que los valores de N y digit sean positivos y realizar los siguientes pasos:
- Si el valor de un dígito es como máximo N , entonces multiplique num por 10 y luego agregue el valor de digit a num y disminuya el valor de N por dígito .
- Además, disminuya el valor del dígito en 1 .
- Multiplique la variable num por 10 y agregue el dígito 0 al final.
- Después de completar los pasos anteriores, imprima el valor de num como el número resultante.
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 largest positive
// number made up of distinct digits
// having the sum of its digits as N
long largestNumber(int N)
{
// If given number is greater
// than 45, print -1
if (N > 45)
return -1;
// Store the required number and
// the digit to be considered
int num = 0, digit = 9;
// Loop until N > 0 and digit > 0
while (N > 0 && digit > 0) {
// If the current digit is
// at most N then, add it
// to number num
if (digit <= N) {
// Update the value of
// num
num *= 10;
num += digit;
// Decrement N by digit
N -= digit;
}
// Consider the next lower
// digit
digit -= 1;
}
// Add 0 at the end and return
// the number num
return num * 10;
}
// Driver Code
int main()
{
int N = 25;
cout << largestNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the largest positive
// number made up of distinct digits
// having the sum of its digits as N
static long largestNumber(int N)
{
// If given number is greater
// than 45, print -1
if (N > 45)
return -1;
// Store the required number and
// the digit to be considered
int num = 0, digit = 9;
// Loop until N > 0 and digit > 0
while (N > 0 && digit > 0)
{
// If the current digit is
// at most N then, add it
// to number num
if (digit <= N)
{
// Update the value of
// num
num *= 10;
num += digit;
// Decrement N by digit
N -= digit;
}
// Consider the next lower
// digit
digit -= 1;
}
// Add 0 at the end and return
// the number num
return num * 10;
}
// Driver Code
public static void main (String[] args)
{
int N = 25;
System.out.print(largestNumber(N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python program for the above approach # Function to find the largest positive # number made up of distinct digits # having the sum of its digits as N def largestNumber(N): # If given number is greater # than 45, print -1 if (N > 45): return -1 # Store the required number and # the digit to be considered num = 0 digit = 9 # Loop until N > 0 and digit > 0 while (N > 0 and digit > 0): # If the current digit is # at most N then, add it # to number num if (digit <= N): # Update the value of # num num *= 10 num += digit # Decrement N by digit N -= digit # Consider the next lower # digit digit -= 1 # Add 0 at the end and return # the number num return num * 10 # Driver Code N = 25 print(largestNumber(N)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the largest positive
// number made up of distinct digits
// having the sum of its digits as N
static long largestNumber(int N)
{
// If given number is greater
// than 45, print -1
if (N > 45)
return -1;
// Store the required number and
// the digit to be considered
int num = 0, digit = 9;
// Loop until N > 0 and digit > 0
while (N > 0 && digit > 0)
{
// If the current digit is
// at most N then, add it
// to number num
if (digit <= N)
{
// Update the value of
// num
num *= 10;
num += digit;
// Decrement N by digit
N -= digit;
}
// Consider the next lower
// digit
digit -= 1;
}
// Add 0 at the end and return
// the number num
return num * 10;
}
// Driver Code
public static void Main()
{
int N = 25;
Console.Write(largestNumber(N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
// Function to find the largest positive
// number made up of distinct digits
// having the sum of its digits as N
function largestNumber(N)
{
// If given number is greater
// than 45, print -1
if (N > 45)
return -1;
// Store the required number and
// the digit to be considered
let num = 0, digit = 9;
// Loop until N > 0 and digit > 0
while (N > 0 && digit > 0)
{
// If the current digit is
// at most N then, add it
// to number num
if (digit <= N)
{
// Update the value of
// num
num *= 10;
num += digit;
// Decrement N by digit
N -= digit;
}
// Consider the next lower
// digit
digit -= 1;
}
// Add 0 at the end and return
// the number num
return num * 10;
}
// Driver Code
let N = 25;
document.write(largestNumber(N));
</script>
Producción:
98710
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por heyiamsurya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA