难度: Medium
Submission
运行时间: 25 ms
内存: 15.9 MB
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
Explain
这个题解的思路是对给定的数字 num 进行因式分解，从 9 到 2 依次枚举因子 i，将 num 中所有因子 i 提取出来，构建最小的因式分解结果。具体做法是，从高到低枚举因子 i，若 num 可以被 i 整除，则将 i 添加到结果的个位，同时将 num 除以 i。在添加因子 i 时，使用 mul 记录当前因子在结果中的位置，每添加一个因子，mul 就乘以 10，保证因子按照从小到大的顺序构建结果。最终，如果 num 被完全分解且结果不超过 2^31-1，则返回构建的最小因式分解结果，否则返回 0。
时间复杂度: O(log(num))
空间复杂度: O(1)
class Solution:
def smallestFactorization(self, num: int) -> int:
if num < 2:
return num
ans, mul = 0, 1
# 从 9 到 2 依次枚举因子 i
for i in range(9, 1, -1):
# 将 num 中所有因子 i 提取出来
while num % i == 0:
num //= i
# 将因子 i 添加到结果的个位，并更新结果
ans = mul * i + ans
# 更新因子在结果中的位置
mul *= 10
# 判断 num 是否被完全分解，且结果是否超过 2^31-1
return ans if num < 2 and ans <= 2**31 - 1 else 0
Explore
在因式分解时选择因子从9到2逆序枚举的主要目的是构建最小的因式分解结果。从大到小的顺序可以确保较大的因数尽可能靠右，从而使得构成的数字尽可能小。如果从2到9正序枚举，较小的因子会被优先使用，导致最高位可能是较小的数字，最终构成的数字会更大。
如果在因式分解过程中`num`最终不为1，而是一个大于1的素数，这意味着`num`无法完全通过2到9的因子进行分解。在此情况下返回0是为了表示无法通过题目要求的因子完全分解`num`。这种处理确保了只有那些可以完全分解的数才返回有效的因式分解结果，保证了结果的正确性和有效性。
直接通过`ans = mul * i + ans`累加的确有可能导致数字溢出，特别是当`ans`逐渐变大，接近32位整数的界限时。为了避免溢出，可以在每次更新`ans`之前检查是否会超过`2**31 - 1`。如果即将超过，应立即停止进一步的计算并返回0，这样可以防止溢出并返回无效的结果。
使用`mul`变量以10的整数次幂形式来控制因子的位置是一种常用的技术，用于确保数字的每一位都正确地反映了其因数。虽然这种方法在大多数情况下是有效的，但在极端情况下（如因式分解结果接近32位整数的上限时），可能会导致乘法操作中的溢出。在这种情况下，应该在每次更新`ans`和`mul`时检查它们的值是否会导致溢出，以确保计算的准确性和结果的有效性。