El menor número k tal que el producto de los dígitos de k es igual a n

Dado un número no negativo n . El problema es encontrar el número k más pequeño tal que el producto de los dígitos de k sea igual a n . Si no se puede formar tal número k , imprima «-1».
Ejemplos: 
 

Input : 100
Output : 455
4*5*5 = 100 and 455 is the
smallest possible number.

Input : 26
Output : -1

Fuente: Preguntado en Amazon Entrevista
 

Método: para cada i = 9 a 2, divida repetidamente n entre i hasta que no se pueda dividir más o la lista de números del 9 al 2 se termine. Además, en el proceso de división, coloque cada dígito i en la pila que divide a n por completo. Después de completar el proceso anterior, verifique si n == 1 o no. De lo contrario, imprima «-1», de lo contrario, forme el número k usando los dígitos de la pila que contiene los dígitos en la misma secuencia que extrajo de la pila. 
 

// C++ implementation to find smallest number k such that
// the product of digits of k is equal to n
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find smallest number k such that
// the product of digits of k is equal to n
long long int smallestNumber(int n)
{
    // if 'n' is a single digit number, then
    // it is the required number
    if (n >= 0 && n <= 9)
        return n;
     
    // stack the store the digits
    stack<int> digits;
     
    // repeatedly divide 'n' by the numbers
    // from 9 to 2 until all the numbers are
    // used or 'n' > 1
    for (int i=9; i>=2 && n > 1; i--)
    {
        while (n % i == 0)
        {
            // save the digit 'i' that divides 'n'
            // onto the stack
            digits.push(i);
            n = n / i;
        }
    }
     
    // if true, then no number 'k' can be formed
    if (n != 1)
        return -1;
 
    // pop digits from the stack 'digits'
    // and add them to 'k'
    long long int k = 0;
    while (!digits.empty())
    {
        k = k*10 + digits.top();
        digits.pop();
    }
     
    // required smallest number
    return k;
}
 
// Driver program to test above
int main()
{
    int n = 100;
    cout << smallestNumber(n);
    return 0;
}

//Java implementation to find smallest number k such that
// the product of digits of k is equal to n
import java.util.Stack;
 
public class GFG {
 
// function to find smallest number k such that
// the product of digits of k is equal to n
    static long smallestNumber(int n) {
        // if 'n' is a single digit number, then
        // it is the required number
        if (n >= 0 && n <= 9) {
            return n;
        }
 
        // stack the store the digits
        Stack<Integer> digits = new Stack<>();
 
        // repeatedly divide 'n' by the numbers
        // from 9 to 2 until all the numbers are
        // used or 'n' > 1
        for (int i = 9; i >= 2 && n > 1; i--) {
            while (n % i == 0) {
                // save the digit 'i' that divides 'n'
                // onto the stack
                digits.push(i);
                n = n / i;
            }
        }
 
        // if true, then no number 'k' can be formed
        if (n != 1) {
            return -1;
        }
 
        // pop digits from the stack 'digits'
        // and add them to 'k'
        long k = 0;
        while (!digits.empty()) {
            k = k * 10 + digits.peek();
            digits.pop();
        }
 
        // required smallest number
        return k;
    }
 
// Driver program to test above
    static public void main(String[] args) {
        int n = 100;
        System.out.println(smallestNumber(n));
    }
}
 
/*This code is contributed by PrinciRaj1992*/

# Python3 implementation to find smallest
# number k such that the product of digits
# of k is equal to n
import math as mt
 
# function to find smallest number k such that
# the product of digits of k is equal to n
def smallestNumber(n):
 
    # if 'n' is a single digit number, then
    # it is the required number
    if (n >= 0 and n <= 9):
        return n
     
    # stack the store the digits
    digits = list()
     
    # repeatedly divide 'n' by the numbers
    # from 9 to 2 until all the numbers are
    # used or 'n' > 1
    for i in range(9,1, -1):
     
        while (n % i == 0):
         
            # save the digit 'i' that
            # divides 'n' onto the stack
            digits.append(i)
            n = n //i
         
    # if true, then no number 'k'
    # can be formed
    if (n != 1):
        return -1
 
    # pop digits from the stack 'digits'
    # and add them to 'k'
    k = 0
    while (len(digits) != 0):
     
        k = k * 10 + digits[-1]
        digits.pop()
     
    # required smallest number
    return k
 
# Driver Code
n = 100
print(smallestNumber(n))
 
# This code is contributed by
# Mohit kumar 29

     
// C# implementation to find smallest number k such that
// the product of digits of k is equal to n
using System;
using System.Collections.Generic;
public class GFG {
  
// function to find smallest number k such that
// the product of digits of k is equal to n
    static long smallestNumber(int n) {
        // if 'n' is a single digit number, then
        // it is the required number
        if (n >= 0 && n <= 9) {
            return n;
        }
  
        // stack the store the digits
        Stack<int> digits = new Stack<int>();
  
        // repeatedly divide 'n' by the numbers
        // from 9 to 2 until all the numbers are
        // used or 'n' > 1
        for (int i = 9; i >= 2 && n > 1; i--) {
            while (n % i == 0) {
                // save the digit 'i' that divides 'n'
                // onto the stack
                digits.Push(i);
                n = n / i;
            }
        }
  
        // if true, then no number 'k' can be formed
        if (n != 1) {
            return -1;
        }
  
        // pop digits from the stack 'digits'
        // and add them to 'k'
        long k = 0;
        while (digits.Count!=0) {
            k = k * 10 + digits.Peek();
            digits.Pop();
        }
  
        // required smallest number
        return k;
    }
  
// Driver program to test above
    static public void Main() {
        int n = 100;
        Console.Write(smallestNumber(n));
    }
}
  
/*This code is contributed by Rajput-Ji*/

<?php
// PHP implementation to find smallest number k such that
// the product of digits of k is equal to n
 
// function to find smallest number k such that
// the product of digits of k is equal to n
function smallestNumber($n)
{
    // if 'n' is a single digit number, then
    // it is the required number
    if ($n >= 0 && $n <= 9)
        return $n;
     
    // stack the store the digits
    $digits = array();
     
    // repeatedly divide 'n' by the numbers
    // from 9 to 2 until all the numbers are
    // used or 'n' > 1
    for ($i = 9; $i >= 2 && $n > 1; $i--)
    {
        while ($n % $i == 0)
        {
            // save the digit 'i' that divides 'n'
            // onto the stack
            array_push($digits,$i);
            $n =(int)( $n / $i);
        }
    }
     
    // if true, then no number 'k' can be formed
    if ($n != 1)
        return -1;
 
    // pop digits from the stack 'digits'
    // and add them to 'k'
    $k = 0;
    while (!empty($digits))
        $k = $k * 10 + array_pop($digits);
     
    // required smallest number
    return $k;
}
 
    // Driver code
    $n = 100;
    echo smallestNumber($n);
 
// This code is contributed by mits
?>

<script>
 
// Javascript implementation to find
// smallest number k such that
// the product of digits of k is equal to n
     
    // function to find smallest number k such that
// the product of digits of k is equal to n
    function smallestNumber(n)
    {
        // if 'n' is a single digit number, then
        // it is the required number
        if (n >= 0 && n <= 9) {
            return n;
        }
   
        // stack the store the digits
        let digits = [];
   
        // repeatedly divide 'n' by the numbers
        // from 9 to 2 until all the numbers are
        // used or 'n' > 1
        for (let i = 9; i >= 2 && n > 1; i--) {
            while (n % i == 0) {
                // save the digit 'i' that divides 'n'
                // onto the stack
                digits.push(i);
                n = Math.floor(n / i);
            }
        }
   
        // if true, then no number 'k' can be formed
        if (n != 1) {
            return -1;
        }
   
        // pop digits from the stack 'digits'
        // and add them to 'k'
        let k = 0;
        while (digits.length!=0) {
            k = k * 10 + digits[digits.length-1];
            digits.pop();
        }
   
        // required smallest number
        return k;
    }
     
    // Driver program to test above
    let n = 100;
    document.write(smallestNumber(n));
     
 
// This code is contributed by patel2127
 
</script>

Producción:  

455

Complejidad de tiempo: O(num), donde num es el tamaño de la pila. 
Complejidad espacial: O(num), donde num es el tamaño de la pila.
Podemos almacenar el número k requerido en una string para números grandes.
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.