Formatted question description: https://leetcode.ca/all/625.html

625. Minimum Factorization

Level

Medium

Description

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

Solution

If a is less than 10, then simply return a. Otherwise, first check the prime factors of a. If there exists a prime factor of a that is greater than 10, then it is impossible to represent a using the multiplication of several one-digit numbers, so return 0.

To find the smallest positive integer b, b must have the shortest length, so consider the maximum possible one-digit factor first. Therefore, loop over i from 9 to 2, and divide a by i until a can’t be divisible by i. Store the factors and append them in the reversing order to form b, and return.

class Solution {
    public int smallestFactorization(int a) {
        if (a < 10)
            return a;
        boolean oneDigitPrime = oneDigitPrime(a);
        if (!oneDigitPrime)
            return 0;
        List<Integer> factors = new ArrayList<Integer>();
        int num = a;
        for (int i = 9; i > 1 && num > 1; i--) {
            while (num % i == 0) {
                num /= i;
                factors.add(i);
            }
        }
        if (factors.size() > 10)
            return 0;
        long newNumLong = 0;
        for (int i = factors.size() - 1; i >= 0; i--)
            newNumLong = newNumLong * 10 + factors.get(i);
        if (newNumLong > Integer.MAX_VALUE)
            return 0;
        else
            return (int) newNumLong;
    }

    public boolean oneDigitPrime(int num) {
        while (num % 2 == 0)
            num /= 2;
        for (int i = 3; i <= 7 && num > 1; i += 2) {
            while (num % i == 0)
                num /= i;
        }
        return num == 1;
    }
}

All Problems

All Solutions