题目描述:
LeetCode 625. Minimum Factorization
Given a positive integer a
, find the smallest positive integer b
whose multiplication of each digit equals to a
.
If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.
Example 1
Input:
48
Output:
68
Example 2
Input:
15
Output:
35
题目大意:
给定正整数a,求各位相乘等于a的最小整数。
若不存在这样的整数,或者超过32位带符号整数范围,则返回0。
解题思路:
解法I 从9到2试除
Python代码:
class Solution(object):
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a == 1: return 1
cnt = [0] * 10
for x in range(9, 1, -1):
while a % x == 0:
cnt[x] += 1
a /= x
if a > 1: return 0
ans = int(''.join(str(n) * cnt[n] for n in range(2, 10)))
return ans <= 0x7FFFFFFF and ans or 0
解法II 因式分解
将a因式分解,若存在大于9的因子,则直接返回0 a的因子包括2, 3, 5, 7四种类型 优先用3构造因子9,然后用2和3构造因子6,最后用2构造因子4 将各因子递增输出
Java代码:
import java.math.BigInteger;
public class Solution {
public int smallestFactorization(int a) {
if (a == 1) return 1;
int cnt[] = new int[10];
while (a > 1) {
for (int x = 2; x <= a; x++) {
if (x > 9) return 0;
if (a % x == 0) {
cnt[x]++;
a /= x;
break;
}
}
}
cnt[9] = cnt[3] / 2;
cnt[3] %= 2;
cnt[8] = cnt[2] / 3;
cnt[2] %= 3;
if (cnt[2] > 0 && cnt[3] > 0) {
cnt[2]--;
cnt[3] = 0;
cnt[6] = 1;
}
if (cnt[2] == 2) {
cnt[2] = 0;
cnt[4] = 1;
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= 9; i++) {
for (int j = 0; j < cnt[i]; j++) {
sb.append(Integer.toString(i));
}
}
String ans = sb.toString();
if (new BigInteger(ans).compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0)
return 0;
return Integer.parseInt(ans);
}
}
本文链接:http://bookshadow.com/weblog/2017/06/18/leetcode-minimum-factorization/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。