Dado un número entero positivo N , la tarea es encontrar el número más pequeño cuya suma de dígitos sea N.
Ejemplo:
Input: N = 10 Output: 19 Explanation: 1 + 9 = 10 = N Input: N = 18 Output: 99 Explanation: 9 + 9 = 18 = N
Enfoque ingenuo:
- Un enfoque ingenuo es ejecutar un ciclo de i comenzando desde 0 y encontrar la suma de dígitos de i y verificar si es igual a N o no.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the smallest
// number whose sum of digits is also N
#include <iostream>
#include <math.h>
using namespace std;
// Function to get sum of digits
int getSum(int n)
{
int sum = 0;
while (n != 0) {
sum = sum + n % 10;
n = n / 10;
}
return sum;
}
// Function to find the smallest
// number whose sum of digits is also N
void smallestNumber(int N)
{
int i = 1;
while (1) {
// Checking if number has
// sum of digits = N
if (getSum(i) == N) {
cout << i;
break;
}
i++;
}
}
// Driver code
int main()
{
int N = 10;
smallestNumber(N);
return 0;
}
Java
// Java program to find the smallest
// number whose sum of digits is also N
class GFG{
// Function to get sum of digits
static int getSum(int n)
{
int sum = 0;
while (n != 0)
{
sum = sum + n % 10;
n = n / 10;
}
return sum;
}
// Function to find the smallest
// number whose sum of digits is also N
static void smallestNumber(int N)
{
int i = 1;
while (1 != 0)
{
// Checking if number has
// sum of digits = N
if (getSum(i) == N)
{
System.out.print(i);
break;
}
i++;
}
}
// Driver code
public static void main(String[] args)
{
int N = 10;
smallestNumber(N);
}
}
// This code is contributed
// by shivanisinghss2110
Python3
# Python3 program to find the smallest # number whose sum of digits is also N # Function to get sum of digits def getSum(n): sum1 = 0; while (n != 0): sum1 = sum1 + n % 10; n = n // 10; return sum1; # Function to find the smallest # number whose sum of digits is also N def smallestNumber(N): i = 1; while (1): # Checking if number has # sum of digits = N if (getSum(i) == N): print(i); break; i += 1; # Driver code N = 10; smallestNumber(N); # This code is contributed by Code_Mech
C#
// C# program to find the smallest
// number whose sum of digits is also N
using System;
class GFG{
// Function to get sum of digits
static int getSum(int n)
{
int sum = 0;
while (n != 0)
{
sum = sum + n % 10;
n = n / 10;
}
return sum;
}
// Function to find the smallest
// number whose sum of digits is also N
static void smallestNumber(int N)
{
int i = 1;
while (1 != 0)
{
// Checking if number has
// sum of digits = N
if (getSum(i) == N)
{
Console.Write(i);
break;
}
i++;
}
}
// Driver code
public static void Main(String[] args)
{
int N = 10;
smallestNumber(N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
//Javascript program to find /the smallest
// number whose sum of digits is also N
// Function to get sum of digits
function getSum(n)
{
let sum = 0;
while (n != 0) {
sum = sum + n % 10;
n = Math.floor(n / 10);
}
return sum;
}
// Function to find the smallest
// number whose sum of digits is also N
function smallestNumber(N)
{
let i = 1;
while (1) {
// Checking if number has
// sum of digits = N
if (getSum(i) == N) {
document.write(i);
break;
}
i++;
}
}
// Driver code
let N = 10;
smallestNumber(N);
// This code is contributed by Mayank Tyagi
</script>
Producción
19
Complejidad temporal: O(N).
Espacio auxiliar: O(1)
Enfoque eficiente:
- Un enfoque eficiente para este problema es una observación. Veamos algunos ejemplos.
- Si N = 10, entonces respuesta = 19
- Si N = 20, entonces respuesta = 299
- Si N = 30, entonces respuesta = 3999
- Entonces, está claro que la respuesta tendrá todos los dígitos como 9 excepto el primero para que obtengamos el número más pequeño.
- Entonces, el enésimo término será =
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the smallest
// number whose sum of digits is also N
#include <iostream>
#include <math.h>
using namespace std;
// Function to find the smallest
// number whose sum of digits is also N
void smallestNumber(int N)
{
cout << (N % 9 + 1)
* pow(10, (N / 9))
- 1;
}
// Driver code
int main()
{
int N = 10;
smallestNumber(N);
return 0;
}
Java
// Java program to find the smallest
// number whose sum of digits is also N
class GFG{
// Function to find the smallest
// number whose sum of digits is also N
static void smallestNumber(int N)
{
System.out.print((N % 9 + 1) *
Math.pow(10, (N / 9)) - 1);
}
// Driver code
public static void main(String[] args)
{
int N = 10;
smallestNumber(N);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to find the smallest # number whose sum of digits is also N # Function to find the smallest # number whose sum of digits is also N def smallestNumber(N): print((N % 9 + 1) * pow(10, (N // 9)) - 1) # Driver code N = 10 smallestNumber(N) # This code is contributed by Code_Mech
C#
// C# program to find the smallest
// number whose sum of digits is also N
using System;
class GFG{
// Function to find the smallest
// number whose sum of digits is also N
static void smallestNumber(int N)
{
Console.WriteLine((N % 9 + 1) *
Math.Pow(10, (N / 9)) - 1);
}
// Driver code
public static void Main()
{
int N = 10;
smallestNumber(N);
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program to find the smallest
// number whose sum of digits is also N
// Function to find the smallest
// number whose sum of digits is also N
function smallestNumber(N)
{
document.write( (N % 9 + 1) * Math.pow(10, parseInt(N / 9, 10)) - 1 );
}
let N = 10;
smallestNumber(N);
</script>
Producción
19
Complejidad del tiempo: O(1)
Espacio auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.