[LeetCode 625] 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

Key Observation:

2. after step 1, the input a is either 1 or > 1.

2a. If > 1, then we know that a must have a prime factor that is bigger than 9. In this case, it is impossible to get a valid factorization, return 0.

2b. if == 1, then either input a is 1 and we do not have any digits or input a is > 1 but reduced to 1 with some digits. Return 1 for the former case, for the latter case, check if the smallest

number formed by all digits fits in 32-bit signed integer, return this number if it does, 0 otherwise.

class Solution {
    public int smallestFactorization(int a) {
        List<Integer> digits = new ArrayList<>();
        for(int i = 9; i >= 2; i--) {
            while(a % i == 0) {
                digits.add(i);
                a /= i;
            }
        }
        if(a > 1) {
            return 0;
        }
        else if(a == 1 && digits.size() == 0) {
            return 1;
        }
        long d = 0;
        for(int i = digits.size() - 1; i >= 0; i--) {
            d = d * 10 + digits.get(i);
        }
        return d > Integer.MAX_VALUE ? 0 : (int)d;
    }
}

The above solution is already optimal. However there is another more complicated way of sloving this problem. We'll go through it here as an exercise.

If the input is < 10, then the output is the input a itself.

If a >= 10, if there is prime factor that is > 10, it is impossible to get a valid answer. In another word, we can only use prime factors 2,3,5,7 to get a valid answer. For 5 and 7, they must form their own digits. For 2 and 3, we can have the following combinations: 2 * 2 = 4, 2 * 2 * 2 = 8, 2 * 3 = 6, 3 * 3 = 9. How we should make an optimal combination is still not clear.

Base on this, we can apply the integer prime factorization algorithm to get all a's prime factors. Then we check if there is any multiple digits prime factor, if there is, return 0. Otherwise,

we try to combine all prime factors from both directions. First from small to big, then from big to small. Then pick the smaller result and do a final check if it fits in 32-bit signed integer range.

class Solution {
    public int smallestFactorization(int a) {        
        if(a < 10) {
            return a;
        }
        List<Integer> primeFactors = new ArrayList<>();
        while(a % 2 == 0) {
            primeFactors.add(2);
            a /= 2;
        }
        for(int i = 3; i <= Math.sqrt(a); i += 2) {
            while(a % i == 0) {
                primeFactors.add(i);
                a /= i;
            }
        }
        if(a > 2) {
            primeFactors.add(a);
        }
        if(primeFactors.size() < 2) {
            return 0;
        }
        int i = 0;
        long v1 = 0;
        List<Integer> ans1 = new ArrayList<>();
        while(i < primeFactors.size()) {
            if(primeFactors.get(i) > 10) {
                v1 = (long)Integer.MAX_VALUE + 1;
                break;
            }
            int d = primeFactors.get(i);
            while(i < primeFactors.size() - 1 && d * primeFactors.get(i + 1) < 10) {
                d = d * primeFactors.get(i + 1);
                i++;
            }
            ans1.add(d);
            i++;
        }
        if(v1 == 0) {
            Collections.sort(ans1);
            for(int j = 0; j < ans1.size(); j++) {
                v1 = v1 * 10 + ans1.get(j);
            }            
        }
        
        i = primeFactors.size() - 1;
        long v2 = 0;
        List<Integer> ans2 = new ArrayList<>();
        while(i >= 0) {
            if(primeFactors.get(i) > 10) {
                v2 = (long)Integer.MAX_VALUE + 1;
                break;
            }
            int d = primeFactors.get(i);
            while(i > 0 && d * primeFactors.get(i - 1) < 10) {
                d = d * primeFactors.get(i - 1);
                i--;
            }
            ans2.add(d);
            i--;
        }
        if(v2 == 0) {
            Collections.sort(ans2);
            for(int j = 0; j < ans2.size(); j++) {
                v2 = v2 * 10 + ans2.get(j);
            }              
        }
  
        long vMin =  Math.min(v1, v2);
        return vMin > Integer.MAX_VALUE ? 0 : (int)vMin;
    }
}

[LeetCode 625] Minimum Factorization

相关推荐