Leetcode: Minimum Factorization

Minimum Factorization



Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/minimum-factorization
// Basic Ideas:
//
// 48 -> [2, 2, 2, 2, 2, 3]
// 15 -> [3, 5]
//
// If n has dividends bigger than 9, it won't work
//
// Now we get all dividends as l[int]. 
// How we can construct the minimum number?
// - smallest digits count
// - smallest digit values
//
// Complexity:
func smallestFactorization(a int) int {
    if a<=1 { return a }
    m := map[int]int{}
    for _, v:=range[]int{2, 3, 5, 7} {
        for a%v == 0 {
            a = int(a/v)
            m[v] += 1
        }
    }
    if a !=1 { return 0 }

    // 2 2 2 -> 8
    if m[2] >= 3 { m[8], m[2] =int(m[2]/3), m[2]%3 }
    // 3 3 -> 9
    if m[3] >=2 { m[9],m[3] = int(m[3]/2), m[3]%2 }
    // 2 3 -> 6
    if m[2]>=1 && m[3]==1 { m[6], m[2], m[3] = 1, m[2]-1, 0 }
    // 2 2 -> 4
    if m[2]==2 { m[2], m[4] = 0, 1 }
    // get the result
    res := 0
    for i:=2; i<10; i++ {
        for m[i] != 0 {
            res = res*10+i
            if res > 2147483647 { return 0 }
            m[i]--
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.