625. 最小因式分解 🔒

题目描述

给定一个正整数 num，找出最小的正整数 x 使得 x 的所有数位相乘恰好等于 num。

如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。

示例 1：

输入：num = 48
输出：68

示例 2：

输入：num = 15
输出：35

提示：

1 <= num <= 2³¹ - 1

解法

方法一：贪心 + 因式分解

思考

要把 \(num\) 拆成若干个 \(2..9\) 的乘积，并使拼成的整数最小。拆法很多，穷举位数不可取。

位数越少、高位越小则数越小，故从 \(9\) 往 \(2\) 尽量整除，把因子从低位写入。若最后剩 \(num>1\) 或溢出 \(32\) 位有符号范围，则无法构成。

我们先判断 \(num\) 是否小于 \(2\)，如果是，直接返回 \(num\)。然后从 \(9\) 开始，尽可能多地将数字分解为 \(9\)，然后分解为 \(8\)，以此类推，直到分解为 \(2\)。如果最后剩下的数字不是 \(1\)，或者结果超过了 \(2^{31} - 1\)，则返回 \(0\)。否则，我们返回结果。

注意，分解后的数字，应该依次填充到结果的个位、十位、百位、千位……上，因此我们需要维护一个变量 \(mul\)，表示当前的位数。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为 \(num\) 的值。

Python3JavaC++Go

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
}

625. 最小因式分解 🔒

题目描述

解法

方法一：贪心 + 因式分解

评论