четверг, 18 февраля 2016 г.

Задача о минимальном числе, составленном из множителей разбиения

На днях наткнулся на небольшую, но интересную задачку. Условие звучит так:
Задано целое десятичное число N такое, что 9 < N < 10^5. Требуется найти такое минимальное положительное десятичное целое число, произведение цифр которого равно числу N. Если такое число найти не удается, требуется вернуть 0.

Например, задано число 20. Его можно разбить на множители несколькими способами, которые подходят под условие задачи (исключаем множители 10 и 20, так как они не являются цифрами, плюс исключаем единицу, так как в данном случае она будет лишь способствовать увеличению числа-результата за счет дополнительного разряда):
1. цифры 4 и 5
2. цифры 2, 2 и 5
Из найденных цифр можно составить несколько чисел. Решением будет число 45, так как оно будет наименьшим среди всех возможных вариантов.