algo-aha

最小因数分解

• https://leetcode.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

int smallestFactorization(int a) {
    if (a < 10) return a;
    // a要分解成单数字因子，且个数越少越好，所以从9到2地尝试分解
    long ans = 0, base = 1;
    for (int i = 9; i >= 2; i--) {
        while (a % i == 0) {
            ans += i * base;
            if (ans > INT_MAX) return 0;
            a /= i;
            base *= 10;
        }
    }
    return (a == 1) ? ans : 0;
}