LeetCode Minimum Factorization

LeetCode 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,要求找一个最小的数b,使得b的各位数字相乘的结果等于a。

很有意思的一个题,考察数学,当时没做出来,参考了这个题

首先,如果a小于10的话,那么最小的b就是a了,否则b就要变成十位数或者百位数。比如a=8,则最小的b就是8,当然b也可以是十位数比如24或者42,但是都大于个位数8自己。

当a大于等于10时,我们需要找a的因子,为了是b最小,则我们希望b的位数越少越好。所以我们要找b的因子应该越大越好。所以我们从最大的因子9开始找起,从9一直找到2,把a的所有因子都找出来。比如48从大到小的因子是8和6,则最终结果就是把因子从小到大组成一个数,即68。

这里有一个问题,48的因子还可以是4和2呀,为什么没有了呢。因为我们从9→2开始找因子的过程中,是用a除以因子得到的商来不断的找。上面48找到8和6的因子之后,商就等于1了,不需要再找因子了,所以结束。

如果在找因子的过程中,发现商变成了一个质数,因为大于10的质数不可能被分解,所以无解,返回0。

代码如下:

class Solution {
public:
	int smallestFactorization(int a) {
		if (a < 10)return a;
		vector<int> factors;
		for (int i = 9; i >= 2; --i) {
			while (a%i == 0) {
				factors.push_back(i);
				a /= i;
			}
		}
		if (a != 1)return 0; // caution
		long long ans = 0;
		for (int i = factors.size() - 1; i >= 0; --i) {
			ans = ans * 10 + factors[i];
		}
		return ans > INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *