内容简介:[LeetCode]Minimum Factorization
题目描述:
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:
Output:
Example 2
Input:
Output:
题目大意:
给定正整数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); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。