Formatted question description: https://leetcode.ca/all/625.html

625. Minimum Factorization

Level

Medium

Description

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

Solution

If a is less than 10, then simply return a. Otherwise, first check the prime factors of a. If there exists a prime factor of a that is greater than 10, then it is impossible to represent a using the multiplication of several one-digit numbers, so return 0.

To find the smallest positive integer b, b must have the shortest length, so consider the maximum possible one-digit factor first. Therefore, loop over i from 9 to 2, and divide a by i until a can’t be divisible by i. Store the factors and append them in the reversing order to form b, and return.

  • class Solution {
        public int smallestFactorization(int a) {
            if (a < 10)
                return a;
            boolean oneDigitPrime = oneDigitPrime(a);
            if (!oneDigitPrime)
                return 0;
            List<Integer> factors = new ArrayList<Integer>();
            int num = a;
            for (int i = 9; i > 1 && num > 1; i--) {
                while (num % i == 0) {
                    num /= i;
                    factors.add(i);
                }
            }
            if (factors.size() > 10)
                return 0;
            long newNumLong = 0;
            for (int i = factors.size() - 1; i >= 0; i--)
                newNumLong = newNumLong * 10 + factors.get(i);
            if (newNumLong > Integer.MAX_VALUE)
                return 0;
            else
                return (int) newNumLong;
        }
    
        public boolean oneDigitPrime(int num) {
            while (num % 2 == 0)
                num /= 2;
            for (int i = 3; i <= 7 && num > 1; i += 2) {
                while (num % i == 0)
                    num /= i;
            }
            return num == 1;
        }
    }
    
  • Todo
    
  • class Solution(object):
      # while loop
      def smallestFactorization(self, a):
        """
        :type a: int
        :rtype: int
        """
        if a < 10:
          return a
        path = []
        k = 9
        while k > 1 and a > 1:
          if a % k == 0:
            path.append(str(k))
            a /= k
          else:
            k -= 1
        path.sort()
        if a > 9 or not path:
          return 0
        ans = int("".join(path))
        return ans if ans <= 0x7fffffff else 0
    
      # normal DFS
      def smallestFactorization(self, a):
        """
        :type a: int
        :rtype: int
        """
        if a <= 1:
          return a
    
        def dfs(num, path):
          if num == 1:
            self.ans = min(self.ans, int("".join(sorted(path))))
            return True
          for i in reversed(range(2, 10)):
            if num % i == 0:
              path.append(str(i))
              if dfs(num / i, path):
                return True
              path.pop()
          return False
    
        self.ans = float("inf")
        dfs(a, [])
        return self.ans if self.ans != float("inf") and self.ans <= 0x7fffffff else 0
    
    

All Problems

All Solutions