Задача: 625. Minimum Factorization
Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.
Пример:
Input: num = 48
Output: 68
👨💻 Алгоритм:
1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.
2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.
3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.
😎 Решение:
def smallestFactorization(num):
if num == 1:
return 1
factors = []
for i in range(9, 1, -1):
while num % i == 0:
factors.append(i)
num //= i
if num > 1:
return 0
result = 0
for factor in reversed(factors):
result = result * 10 + factor
if result > 2**31 - 1:
return 0
return result
👉Новости 👉Платформа