# 算法设计：最小数k，以使k的数字乘积等于n

2021年3月10日16:19:45 发表评论 754 次浏览

## 本文概述

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

Input : 26
Output : -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), 其中