Dado un número ‘n’, encuentre el número más pequeño ‘p’ tal que si multiplicamos todos los dígitos de ‘p’, obtengamos ‘n’. El resultado ‘p’ debe tener un mínimo de dos dígitos.
Ejemplos:
Input: n = 36 Output: p = 49 // Note that 4*9 = 36 and 49 is the smallest such number Input: n = 100 Output: p = 455 // Note that 4*5*5 = 100 and 455 is the smallest such number Input: n = 1 Output:p = 11 // Note that 1*1 = 1 Input: n = 13 Output: Not Possible
Para un n dado, a continuación se muestran los dos casos a considerar.
Caso 1: n < 10 Cuando n es menor que 10, la salida siempre es n+10. Por ejemplo, para n = 7, la salida es 17. Para n = 9, la salida es 19.
Caso 2: n >= 10 Encuentre todos los factores de n que estén entre 2 y 9 (ambos inclusive). La idea es comenzar a buscar desde 9 para que la cantidad de dígitos en el resultado se minimice. Por ejemplo, 9 es preferible a 33 y 8 es preferible a 24.
Almacene todos los factores encontrados en una array. La array contendría dígitos en orden no creciente, así que finalmente imprima la array en orden inverso.
A continuación se muestra la implementación del concepto anterior.
C++
#include<bits/stdc++.h>
using namespace std;
// Maximum number of digits in output
#define MAX 50
// prints the smallest number
// whose digits multiply to n
void findSmallest(int n)
{
int i, j = 0;
// To store digits of result
// in reverse order
int res[MAX];
// Case 1: If number is smaller than 10
if (n < 10)
{
cout << n + 10;
return;
}
// Case 2: Start with 9 and
// try every possible digit
for (i = 9; i > 1; i--)
{
// If current digit divides n, then store all
// occurrences of current digit in res
while (n % i == 0)
{
n = n / i;
res[j] = i;
j++;
}
}
// If n could not be broken
// in form of digits (prime factors
// of n are greater than 9)
if (n > 10)
{
cout << "Not possible";
return;
}
// Print the result array in reverse order
for (i = j - 1; i >= 0; i--)
cout << res[i];
}
// Driver Code
int main()
{
findSmallest(7);
cout << "\n";
findSmallest(36);
cout << "\n";
findSmallest(13);
cout << "\n";
findSmallest(100);
return 0;
}
// This code is contributed by Code_Mech
C
#include<stdio.h>
// Maximum number of digits in output
#define MAX 50
// prints the smallest number whose digits multiply to n
void findSmallest(int n)
{
int i, j=0;
int res[MAX]; // To store digits of result in reverse order
// Case 1: If number is smaller than 10
if (n < 10)
{
printf("%d", n+10);
return;
}
// Case 2: Start with 9 and try every possible digit
for (i=9; i>1; i--)
{
// If current digit divides n, then store all
// occurrences of current digit in res
while (n%i == 0)
{
n = n/i;
res[j] = i;
j++;
}
}
// If n could not be broken in form of digits (prime factors of n
// are greater than 9)
if (n > 10)
{
printf("Not possible");
return;
}
// Print the result array in reverse order
for (i=j-1; i>=0; i--)
printf("%d", res[i]);
}
// Driver program to test above function
int main()
{
findSmallest(7);
printf("\n");
findSmallest(36);
printf("\n");
findSmallest(13);
printf("\n");
findSmallest(100);
return 0;
}
Java
// Java program to find the smallest number whose
// digits multiply to a given number n
import java.io.*;
class Smallest
{
// Function to prints the smallest number whose
// digits multiply to n
static void findSmallest(int n)
{
int i, j=0;
int MAX = 50;
// To store digits of result in reverse order
int[] res = new int[MAX];
// Case 1: If number is smaller than 10
if (n < 10)
{
System.out.println(n+10);
return;
}
// Case 2: Start with 9 and try every possible digit
for (i=9; i>1; i--)
{
// If current digit divides n, then store all
// occurrences of current digit in res
while (n%i == 0)
{
n = n/i;
res[j] = i;
j++;
}
}
// If n could not be broken in form of digits (prime factors of n
// are greater than 9)
if (n > 10)
{
System.out.println("Not possible");
return;
}
// Print the result array in reverse order
for (i=j-1; i>=0; i--)
System.out.print(res[i]);
System.out.println();
}
// Driver program
public static void main (String[] args)
{
findSmallest(7);
findSmallest(36);
findSmallest(13);
findSmallest(100);
}
}
// Contributed by Pramod Kumar
Python3
# Python code to find the smallest number
# whose digits multiply to give n
# function to print the smallest number whose
# digits multiply to n
def findSmallest(n):
# Case 1 - If the number is smaller than 10
if n < 10:
print (n+10)
return
# Case 2 - Start with 9 and try every possible digit
res = [] # to sort digits
for i in range(9,1,-1):
# If current digit divides n, then store all
# occurrences of current digit in res
while n % i == 0:
n = n / i
res.append(i)
# If n could not be broken in the form of digits
# prime factors of n are greater than 9
if n > 10:
print ("Not Possible")
return
# Print the number from result array in reverse order
n = res[len(res)-1]
for i in range(len(res)-2,-1,-1):
n = 10 * n + res[i]
print (n)
# Driver Code
findSmallest(7)
findSmallest(36)
findSmallest(13)
findSmallest(100)
# This code is contributed by Harshit Agrawal
C#
// C# program to find the smallest number whose
// digits multiply to a given number n
using System;
class GFG {
// Function to prints the smallest number
// whose digits multiply to n
static void findSmallest(int n)
{
int i, j=0;
int MAX = 50;
// To store digits of result in
// reverse order
int []res = new int[MAX];
// Case 1: If number is smaller than 10
if (n < 10)
{
Console.WriteLine(n + 10);
return;
}
// Case 2: Start with 9 and try every
// possible digit
for (i = 9; i > 1; i--)
{
// If current digit divides n, then
// store all occurrences of current
// digit in res
while (n % i == 0)
{
n = n / i;
res[j] = i;
j++;
}
}
// If n could not be broken in form of
// digits (prime factors of n
// are greater than 9)
if (n > 10)
{
Console.WriteLine("Not possible");
return;
}
// Print the result array in reverse order
for (i = j-1; i >= 0; i--)
Console.Write(res[i]);
Console.WriteLine();
}
// Driver program
public static void Main ()
{
findSmallest(7);
findSmallest(36);
findSmallest(13);
findSmallest(100);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the
// smallest number whose
// digits multiply to a
// given number n prints the
// smallest number whose digits
// multiply to n
function findSmallest($n)
{
// To store digits of
// result in reverse order
$i;
$j = 0;
$res;
// Case 1: If number is
// smaller than 10
if ($n < 10)
{
echo $n + 10;
return;
}
// Case 2: Start with 9 and
// try every possible digit
for ($i = 9; $i > 1; $i--)
{
// If current digit divides
// n, then store all
// occurrences of current
// digit in res
while ($n % $i == 0)
{
$n = $n / $i;
$res[$j] = $i;
$j++;
}
}
// If n could not be broken
// in form of digits
// (prime factors of n
// are greater than 9)
if ($n > 10)
{
echo "Not possible";
return;
}
// Print the result
// array in reverse order
for ($i = $j - 1; $i >= 0; $i--)
echo $res[$i];
}
// Driver Code
findSmallest(7);
echo "\n";
findSmallest(36);
echo "\n";
findSmallest(13);
echo "\n";
findSmallest(100);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the smallest number whose
// digits multiply to a given number n
// Maximum number of digits in output
// prints the smallest number
// whose digits multiply to n
function findSmallest(n)
{
let i, j = 0;
// To store digits of result
// in reverse order
let res = new Array(50);
// Case 1: If number is smaller than 10
if (n < 10)
{
document.write(n + 10);
return;
}
// Case 2: Start with 9 and
// try every possible digit
for (i = 9; i > 1; i--)
{
// If current digit divides n, then store all
// occurrences of current digit in res
while (n % i == 0)
{
n = Math.floor(n / i);
res[j] = i;
j++;
}
}
// If n could not be broken
// in form of digits (prime factors
// of n are greater than 9)
if (n > 10)
{
document.write("Not possible");
return;
}
// Print the result array in reverse order
for (i = j - 1; i >= 0; i--)
document.write(res[i]);
}
// Driver Code
findSmallest(7);
document.write("<br>");
findSmallest(36);
document.write("<br>");
findSmallest(13);
document.write("<br>");
findSmallest(100);
// This code is contributed by Mayank Tyagi
</script>
Producción:
17 49 Not possible 455
Complejidad de tiempo: O (log 2 n * 10)
Espacio Auxiliar: O(MAX)
Este artículo es una contribución de Ashish Bansal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA