Задача: 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.
😎 Решение:
public class Solution {
public int smallestFactorization(int num) {
if (num == 1) return 1;
List<Integer> factors = new ArrayList<>();
for (int i = 9; i >= 2; i--) {
while (num % i == 0) {
factors.add(i);
num /= i;
}
}
if (num > 1) return 0;
long result = 0;
for (int i = factors.size() - 1; i >= 0; i--) {
result = result * 10 + factors.get(i);
if (result > Integer.MAX_VALUE) return 0;
}
return (int) result;
}
}👉Новости 👉Платформа