Encuentra el número más pequeño tal que la suma de sus dígitos sea N y sea divisible por 
.
Ejemplos:
Input : N = 5 Output : 500000 500000 is the smallest number divisible by 10^5 and sum of digits as 5. Input : N = 20 Output : 29900000000000000000000
Explicación
Para hacer un número divisible por necesitamos al menos N ceros al final del número. Para hacer el número más pequeño, agregamos exactamente N ceros al final del número. Ahora, debemos asegurarnos de que la suma de los dígitos sea N. Para esto, intentaremos que la longitud del número sea lo más pequeña posible para obtener la respuesta. Por lo tanto, seguimos insertando 9 en el número hasta que la suma no exceda N. Si nos queda algún resto, lo mantenemos como el primer dígito (el más significativo) para que el número resultante se minimice.
El enfoque funciona bien para todas las subtareas, pero hay dos casos extremos:
1. El primero es que el número final puede no encajar en los tipos de datos presentes en C++/Java. Como solo necesitamos generar el número, podemos usar strings para almacenar la respuesta.
2. El único caso de esquina donde la respuesta es 0 es N = 0.
3. No hay casos donde la respuesta no existe.
C++
// CPP program to find smallest
// number to find smallest number
// with N as sum of digits and
// divisible by 10^N.
#include <bits/stdc++.h>
using namespace std;
void digitsNum(int N)
{
// If N = 0 the string will be 0
if (N == 0)
cout << "0\n";
// If n is not perfectly divisible
// by 9 output the remainder
if (N % 9 != 0)
cout << (N % 9);
// Print 9 N/9 times
for (int i = 1; i <= (N / 9); ++i)
cout << "9";
// Append N zero's to the number so
// as to make it divisible by 10^N
for (int i = 1; i <= N; ++i)
cout << "0";
cout << "\n";
}
// Driver Code
int main()
{
int N = 5;
cout << "The number is : ";
digitsNum(N);
return 0;
}
Java
// Java program to find smallest
// number to find smallest number
// with N as sum of digits and
// divisible by 10^N.
import java.io.*;
class GFG
{
static void digitsNum(int N)
{
// If N = 0 the string will be 0
if (N == 0)
System.out.println("0");
// If n is not perfectly divisible
// by 9 output the remainder
if (N % 9 != 0)
System.out.print((N % 9));
// Print 9 N/9 times
for (int i = 1; i <= (N / 9); ++i)
System.out.print("9");
// Append N zero's to the number so
// as to make it divisible by 10^N
for (int i = 1; i <= N; ++i)
System.out.print("0");
System.out.print("" );
}
// Driver Code
public static void main (String[] args)
{
int N = 5;
System.out.print("The number is : ");
digitsNum(N);
}
}
// This code is contributed by vt_m
Python3
# Python program to find smallest
# number to find smallest number
# with N as sum of digits and
# divisible by 10^N.
import math
def digitsNum(N):
# If N = 0 the string will be 0
if (N == 0) :
print("0", end = "")
# If n is not perfectly divisible
# by 9 output the remainder
if (N % 9 != 0):
print (N % 9, end ="")
# Print 9 N/9 times
for i in range( 1, int(N / 9) + 1) :
print("9", end = "")
# Append N zero's to the number so
# as to make it divisible by 10^N
for i in range(1, N + 1) :
print("0", end = "")
print()
# Driver Code
N = 5
print("The number is : ",end="")
digitsNum(N)
# This code is contributed by Gitanjali.
C#
// C# program to find smallest
// number to find smallest number
// with N as sum of digits and
// divisible by 10^N.
using System;
class GFG
{
static void digitsNum(int N)
{
// If N = 0 the string will be 0
if (N == 0)
Console.Write("0");
// If n is not perfectly divisible
// by 9 output the remainder
if (N % 9 != 0)
Console.Write((N % 9));
// Print 9 N/9 times
for (int i = 1; i <= (N / 9); ++i)
Console.Write("9");
// Append N zero's to the number so
// as to make it divisible by 10^N )
for (int i = 1; i <= N; ++i)
Console.Write("0");
Console.WriteLine("" );
}
// Driver Code
public static void Main ()
{
int N = 5;
Console.Write("The number is : ");
digitsNum(N);
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find smallest
// number to find smallest number
// with N as sum of digits and
// divisible by 10^N.
function digitsNum($N)
{
// If N = 0 the string will be 0
if ($N == 0)
echo "0\n";
// If n is not perfectly divisible
// by 9 output the remainder
if ($N % 9 != 0)
echo ($N % 9);
// Print 9 N/9 times
for ( $i = 1; $i <= ($N / 9); ++$i)
echo "9";
// Append N zero's to the number so
// as to make it divisible by 10^N
for ($i = 1; $i <= $N; ++$i)
echo "0";
echo "\n";
}
// Driver Code
$N = 5;
echo "The number is : ";
digitsNum($N);
// This code is contributed by ajit.
?>
Javascript
<script>
// JavaScript program to find smallest
// number to find smallest number
// with N as sum of digits and
// divisible by 10^N.
function digitsNum(N)
{
// If N = 0 the string will be 0
if (N == 0) document.write("0\n");
// If n is not perfectly divisible
// by 9 output the remainder
if (N % 9 != 0) document.write(N % 9);
// Print 9 N/9 times
for (var i = 1; i <= N / 9; ++i) document.write("9");
// Append N zero's to the number so
// as to make it divisible by 10^N
for (var i = 1; i <= N; ++i) document.write("0");
document.write("\n");
}
// Driver Code
var N = 5;
document.write("The number is : ");
digitsNum(N);
// This code is contributed by rrrtnx.
</script>
Producción :
The number is : 500000
Complejidad de tiempo : O(N)