AC solution using dynamic programming (no math), Python


  • 0
    S

    Note: I have also figured out a more efficient and simple backtracking algorithm with only 99ms in Python. Please check backtracking solution, where C++ and Python implementions are provided.

    We test every possible (m,n) such that a=m*n. Then we get a solution s by concatenating m and n. However, m and n may themselves have multiple digits, which require further factorization. Therefore, a recursive method is used. After we get all the possible s, return the minimum one.

    Note that in this recursive tree, we may encounter the same number for factorization. Therefore, a memoization trick is adopted to form a dynamic programming method.

    class Solution(object):
        
        def smallestFactorization(self, a):
            """
            :type a: int
            :rtype: int
            """
            self.memory = {} # memory[k] is the Minimum Factorization of k
            return self.dp(a)
            
        def dp(self, k):
            if k < 10:
                return k
            if k in self.memory:
                return self.memory[k]
            # here we test every possible factorization of k into k = m * n
            # and find the minumum integer composed of m and n if any
            s = int(math.sqrt(k))
            factorizations = []
            for m in range(s, 1, -1):
                if k % m == 0:
                    n = k // m
                    left = self.dp(m)
                    right = self.dp(n)
                    if left != 0 and right != 0:    # only m and n both have answers
                        d = 0   # find the number of digits of right
                        t = right
                        while t > 0:
                            d += 1
                            t = t // 10
                        r = left * 10 ** d + right # for example, 123 and 247 => 123247
                        if r <= 2**31 - 1: # fit in 32-bit signed integer
                            factorizations.append(r)
            if factorizations:  # if we have found any legal solution
                self.memory[k] = min(factorizations)
            else:
                self.memory[k] = 0
            return self.memory[k]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.