| comments | true | ||
|---|---|---|---|
| difficulty | 中等 | ||
| edit_url | https://github.com/doocs/leetcode/edit/main/solution/0600-0699/0625.Minimum%20Factorization/README.md | ||
| tags |
|
给定一个正整数 num，找出最小的正整数 x 使得 x 的所有数位相乘恰好等于 num。
如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。
示例 1：
输入：num = 48 输出：68
示例 2：
输入：num = 15 输出：35
提示：
1 <= num <= 231 - 1
我们先判断
注意，分解后的数字，应该依次填充到结果的个位、十位、百位、千位……上，因此我们需要维护一个变量
$mul$ ，表示当前的位数。
时间复杂度
class Solution:
def smallestFactorization(self, num: int) -> int:
if num < 2:
return num
ans, mul = 0, 1
for i in range(9, 1, -1):
while num % i == 0:
num //= i
ans = mul * i + ans
mul *= 10
return ans if num < 2 and ans <= 2**31 - 1 else 0class Solution {
public int smallestFactorization(int num) {
if (num < 2) {
return num;
}
long ans = 0, mul = 1;
for (int i = 9; i >= 2; --i) {
if (num % i == 0) {
while (num % i == 0) {
num /= i;
ans = mul * i + ans;
mul *= 10;
}
}
}
return num < 2 && ans <= Integer.MAX_VALUE ? (int) ans : 0;
}
}class Solution {
public:
int smallestFactorization(int num) {
if (num < 2) {
return num;
}
long long ans = 0, mul = 1;
for (int i = 9; i >= 2; --i) {
if (num % i == 0) {
while (num % i == 0) {
num /= i;
ans = mul * i + ans;
mul *= 10;
}
}
}
return num < 2 && ans <= INT_MAX ? ans : 0;
}
};func smallestFactorization(num int) int {
if num < 2 {
return num
}
ans, mul := 0, 1
for i := 9; i >= 2; i-- {
if num%i == 0 {
for num%i == 0 {
num /= i
ans = mul*i + ans
mul *= 10
}
}
}
if num < 2 && ans <= math.MaxInt32 {
return ans
}
return 0
}