625.Minimum Factorization

Tags: Medium Recursion Math

Links: https://leetcode-cn.com/problems/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

---

class Solution {
public:
    int smallestFactorization(int a) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (a < 10) return a; //只有一位数字直接返回

        int n = a;
        string res;
        for (int i = 9; i >= 2; --i) {
            while (n % i == 0) {
                res += to_string(i);
                n /= i;
            }
        }
        if (n != 1) return 0; //如果n最终不为1，则是质数

        reverse(res.begin(), res.end());
        if (res.size() > 9) return 0;
        long long digit = stoll(res);
        if (digit > INT_MAX) return 0;
        return digit;
    }
};

为了让最终的结果最小（现在只考虑结果存在的情况），那么位数越少越好，为了让位数越少，那么最优策略就是让每一位的数字尽可能的大一些，所以从因子9开始。因为要求的是最终结果的每一位乘积与数字a相等，那么每一个被分解到结果的因子都不能超过9.所以最后如果分解完a不为1，那么结果肯定不存在。