Problem statement

https://leetcode.com/problems/minimum-factorization/

Solution

We need to factor our number into numbers between 2 and 9. Also, we need to put big number to the end and small number to the beginning. For example, if our number is divisible by 9, we need to put 9 to the end, then we put 8, 7 and so on. Why we do in in this order, because the first digits should be as small as possible.

Complexity

Time complexity is O(log^2 a), because each time we add to the beginning of string, we can do O(log a) if we reverse it in the end. Space complexity is O(log a).

Code

class Solution:
    def smallestFactorization(self, a):
        if a == 1: return 1
        sol = ""
        for i in range(9, 1, -1):
            while a % i == 0:
                sol, a = str(i) + sol, a//i

        if a != 1: return 0

        sol = int(sol)
        return sol if sol < 1<<31 else 0