Java Solution, result array


  • 15

    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.


Log in to reply
 

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