Python, Straightforward with Explanation


  • 2

    Suppose N > 1. Let's greedily try to divide N by 9, 8, 7, ..., 2. If we can't divide by some factor here (eg. N = 13) then it's invalid.

    Otherwise, we have some set of digits in descending order whose product equals N. This set is also the smallest possible size (*proof below.) Let's write these digits in sorted order. If it would overflow a 32 bit int, we'll write zero instead.

    Let's prove the set is smallest. If N has factors of 5 or 7, there's only one way to write them. Also, if N = 2^(3w + x) + 3^(2y + z) where 0 <= x < 3 and 0 <= z < 2, then writing 8's and 9's are at least as efficient as optimal. So now we want to write 2^x * 3^z only. If x = 0 or z = 0 we're fine writing 9, 3 or 8, 4, 2. If (x, z) = (1, 1) then we'll write a 6 optimally; if (x, z) = (2, 1) then we'll write 6 * 2 which can't be beaten.

    def smallestFactorization(self, N):
        if N == 1:
            return 1
            
        A = []
        while N > 1:
            for d in xrange(9, 1, -1):
                if N % d == 0:
                    N /= d
                    A.append(d)
                    break
            else:
                return 0
        
        ans = int("".join(map(str, A[::-1])))
        return ans if ans < 2**31 else 0
    

  • 0
    D
    This post is deleted!

Log in to reply
 

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