Java Solution, result array


  • 16

    Reference: http://www.geeksforgeeks.org/find-smallest-number-whose-digits-multiply-given-number-n/

    public class Solution {
        public int smallestFactorization(int n) {
            // Case 1: If number is smaller than 10
            if (n < 10) return n;
            
            // Case 2: Start with 9 and try every possible digit
            List<Integer> res = new ArrayList<>();
            for (int i = 9; i > 1; i--) {
                // If current digit divides n, then store all
                // occurrences of current digit in res
                while (n % i == 0) {
                    n = n / i;
                    res.add(i);
                }
            }
    
            // If n could not be broken in form of digits
            if (n != 1) return 0;
    
            // Get the result from the array in reverse order
            long result = 0;
            for (int i = res.size() - 1; i >= 0; i--) {
                result = result * 10 + res.get(i);
                if (result > Integer.MAX_VALUE) return 0;
            }
            
            return (int)result;
        }
    }
    

  • 7

    Here's mine, similar idea but simpler.

    int smallestFactorization(int a) {
        if (a < 10) return a;
        long res = 0;
        for (long i = 9, f = 1; i > 1; i--)
            while (a % i == 0) {
                res += i * f;
                if (res > INT_MAX) return 0;
                a /= i;
                f *= 10;
            }
        return a == 1 ? res : 0;
    }
    

  • 0
    I

    single loop.

            int ans = 0;
            for (int i = 1, d = 9; a > 1 && d > 1;) {
                if (a % d > 0) {
                    d--;
                } else {
                    a /= d;
                    if (d > (Integer.MAX_VALUE - ans) / i) return 0;
                    ans += d * i;
                    i *= 10;
                }
            }
            return a == 1 ? Math.max(1, ans) : 0;
    

  • 0
    F

    Great Solution! Just FYI, if you use a StringBuilder rather than an ArrayList, then you can utilize Long.ParseLong() to get the integer, thus saving you from writing your own integer conversion function.


  • 0
    W

    @shawngao simple and clear. Python version.

    class Solution(object):
        def smallestFactorization(self, a):
            """
            :type a: int
            :rtype: int
            """
            if a<10: return a
    
            INT_MAX=pow(2,31)-1
    
            res=0
            i,f=9,1
            for i in xrange(9,1,-1):
                while not a%i:
                    res+=i*f
                    if res>INT_MAX: return 0
                    a/=i
                    f*=10
    
            return res if a==1 else 0

Log in to reply
 

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