Question

625. Minimum Factorization

中文文档

Description

Given a positive integer num, return _the smallest positive integer _x_ whose multiplication of each digit equals _num. If there is no answer or the answer is not fit in 32-bit signed integer, return 0.

 

Example 1:

Input: num = 48
Output: 68

Example 2:

Input: num = 15
Output: 35

 

Constraints:

• 1 <= num <= 231 - 1

Solutions

Solution 1

class Solution:
  def smallestFactorization(self, num: int) -> int:
    if num < 2:
      return num
    ans, mul = 0, 1
    for i in range(9, 1, -1):
      while num % i == 0:
        num //= i
        ans = mul * i + ans
        mul *= 10
    return ans if num < 2 and ans <= 2**31 - 1 else 0

class Solution {
  public int smallestFactorization(int num) {
    if (num < 2) {
      return num;
    }
    long ans = 0, mul = 1;
    for (int i = 9; i >= 2; --i) {
      if (num % i == 0) {
        while (num % i == 0) {
          num /= i;
          ans = mul * i + ans;
          mul *= 10;
        }
      }
    }
    return num < 2 && ans <= Integer.MAX_VALUE ? (int) ans : 0;
  }
}

class Solution {
public:
  int smallestFactorization(int num) {
    if (num < 2) {
      return num;
    }
    long long ans = 0, mul = 1;
    for (int i = 9; i >= 2; --i) {
      if (num % i == 0) {
        while (num % i == 0) {
          num /= i;
          ans = mul * i + ans;
          mul *= 10;
        }
      }
    }
    return num < 2 && ans <= INT_MAX ? ans : 0;
  }
};

func smallestFactorization(num int) int {
  if num < 2 {
    return num
  }
  ans, mul := 0, 1
  for i := 9; i >= 2; i-- {
    if num%i == 0 {
      for num%i == 0 {
        num /= i
        ans = mul*i + ans
        mul *= 10
      }
    }
  }
  if num < 2 && ans <= math.MaxInt32 {
    return ans
  }
  return 0
}