算法设计：最小数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

资源：在亚马逊采访中问

推荐：请尝试以下方法{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#

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

输出如下：

455

时间复杂度：

O(num), 其中

数

是堆栈的大小。

空间复杂度：

O(num), 其中

数

是堆栈的大小。

我们可以存储所需的号码ķ以字符串表示大数。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。