# Python, Straightforward with Explanation

• 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
``````

• This post is deleted!

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