class Solution {
public:
string smallestNumber(long long n) {
}
};
2847. 给定数字乘积的最小数字
给定一个 正 整数 n，返回一个字符串，表示 最小的正整数，使其各位数字的乘积等于 n ，如果不存在这样的数字，则返回 "-1" 。
示例 1：
输入：n = 105 输出："357" 解释：3 * 5 * 7 = 105。可以证明，357 是乘积等于 105 的最小数字。因此答案为 "105"。
示例 2：
输入：n = 7 输出："7" 解释：由于 7 只有一位数字，其各位数字的乘积为 7。由于数字 1 到 6 的乘积分别为 1 到 6，所以答案为 "7"。可以证明 7 是乘积等于 7 的最小数字。
示例 3：
输入：n = 44 输出："-1" 解释：可以证明，没有数字的各位数字乘积等于 44。因此答案为 "-1"。
提示：
1 <= n <= 1018原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-10-16 17:30:12
func smallestNumber(n int64) string {
cnt := [10]int{}
for i := 9; i > 1; i-- {
for n%int64(i) == 0 {
cnt[i]++
n /= int64(i)
}
}
if n != 1 {
return "-1"
}
sb := &strings.Builder{}
for i := 2; i < 10; i++ {
for j := 0; j < cnt[i]; j++ {
sb.WriteByte(byte(i) + '0')
}
}
ans := sb.String()
if len(ans) > 0 {
return ans
}
return "1"
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-10-16 17:29:57
class Solution {
public:
string smallestNumber(long long n) {
int cnt[10]{};
for (int i = 9; i > 1; --i) {
while (n % i == 0) {
n /= i;
++cnt[i];
}
}
if (n > 1) {
return "-1";
}
string ans;
for (int i = 2; i < 10; ++i) {
ans += string(cnt[i], '0' + i);
}
return ans == "" ? "1" : ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.3 MB, 提交时间: 2023-10-16 17:29:34
class Solution {
public String smallestNumber(long n) {
int[] cnt = new int[10];
for (int i = 9; i > 1; --i) {
while (n % i == 0) {
++cnt[i];
n /= i;
}
}
if (n > 1) {
return "-1";
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i < 10; ++i) {
while (cnt[i] > 0) {
sb.append(i);
--cnt[i];
}
}
String ans = sb.toString();
return ans.isEmpty() ? "1" : ans;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.9 MB, 提交时间: 2023-10-16 17:29:05
class Solution:
def smallestNumber(self, n: int) -> str:
# 其实就是分解质因数，分解成个位数相乘
if n == 1: return "1"
lis = []
for i in range(9, 1, -1):
while n % i == 0:
n //= i
lis.append(i)
return "".join(str(i) for i in lis[::-1]) if n == 1 else "-1"