算法设计（最小数k，以使k的数字乘积等于n） _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
的PHP

给定一个非负数n。问题是找到最小的数字?这样数字的乘积?等于n。如果没有这样的数字?可以形成然后打印" -1"。
例子：

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

【算法设计（最小数k，以使k的数字乘积等于n）】资源：在亚马逊采访中问
推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法：对于每个一世= 9比2, 反复除法nby一世直到无法进一步划分或来自的数字列表为止9to2完成。另外, 在除法过程中将每个数字一世到划分的堆栈上n完全。完成上述过程后, 检查n == 1。如果不是, 则打印" -1", 否则形成数字?使用包含从堆栈中弹出的数字顺序相同的数字的堆栈中的数字。
C ++

// 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

//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

# 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 // 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 ?>

输出如下：