625. 最小因式分解 🔒
题目描述
给定一个正整数 a
,找出最小的正整数 b
使得 b
的所有数位相乘恰好等于 a
。
如果不存在这样的结果或者结果不是 32 位有符号整数,返回 0。
样例 1
输入:
48
输出:
68
样例 2
输入:
15
输出:
35
解法
方法一:贪心 + 因式分解
我们先判断 $num$ 是否小于 $2$,如果是,直接返回 $num$。然后从 $9$ 开始,尽可能多地将数字分解为 $9$,然后分解为 $8$,以此类推,直到分解为 $2$。如果最后剩下的数字不是 $1$,或者结果超过了 $2^{31} - 1$,则返回 $0$。否则,我们返回结果。
注意,分解后的数字,应该依次填充到结果的个位、十位、百位、千位……上,因此我们需要维护一个变量 $mul$,表示当前的位数。
时间复杂度 $O(\log n)$,空间复杂度 $O(1)$。其中 $n$ 为 $num$ 的值。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|