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。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时3MS。]]>