Найти количество N-значных чисел, у которых сумма цифр равна их произведению (оптимизировать код)

Question

Нужно: Найти количество N-значных чисел, у которых сумма цифр равна их произведению (оптимизировать код)

Моя неудачная попытка (Код медленный):

def cond(a):
    sum = 0
    mult = 1
    while a > 0:
        mult *= a % 10
        sum += a % 10
        a = int(a / 10)

    return sum == mult


def foo(n):
    n = int(n)
    if n == 1:
        return "10 0"

    req_num = 10**n
    prev_num = 10**(n-1)

    min_num = None
    counter = 0

    for i in range(prev_num, req_num):
        if cond(i):
            print(i)
            counter += 1
            if min_num is None:
                min_num = i

    return str(counter) + " " + str(min_num)


print(foo(3))

Для 8-значных и выше чисел не справляется. Как можно улучшить алгоритм? Я нагуглил решение этой проблемы на C++, но не могу перевести код на Python и вообще понять алгоритм, который там используется: https://www.cyberforum.ru/cpp-beginners/thread1972973.html Буду очень благодарен, если кто-то детально опишет используемый там алгоритм. Понял только то, что там как-то используются сочетания к отсортированным числам, благодаря чему количество вычислений уменьшается.

Answer 1

Упростил:

Если n=1, то все 10 чисел являются искомыми, минимальное - 0.
Перебираем все наборы чисел от 1 до 9 включительно.
Если количество цифр n, а их сумма и произведение равны n, то увеличиваем ответ на число перестановок с повторениями для данного набора.
Делаем отсечение по достижению или превышению произведения и по слишком маленькой сумме.
Первый найденный набор образует минимальное число.

Изначальный алгоритм:

Перебираем все различные наборы чисел от 2 до 9 (включительно), произведение которых равно n, а сумма - количеству чисел в наборе (обозначим k).
Для каждого такого набора чисел считаем число сочетаний из n по k и умножаем на количество различных перестановок с повторениями для данного набора.
Суммируем все числа из прошлого пункта.

Ещё есть особый случай - для однозначных чисел решением является ещё и 0.

Answer 2

Вышел такой код. Следуя ответу @Quertiy, можно сделать лучше, но не знаю как.

def check(number):
    s, m = 0, 1
    for digit in str(number) :
        digit = int(digit)
        s += digit
        m *= digit
    return s == m

# input n
while True :
    n = input("Введите N: ")
    if n.isdigit() :
        n = int(n)
        break
    else :
        print("Допустимы только натуральные числа!")

numbers = range(int("1" * n), int("1" + "0" * n))
numbers = filter(lambda x: "0" not in str(x), numbers)
numbers = tuple(filter(lambda x: check(x), numbers))

print(len(numbers))

Пример:

Введите N: 8
224

БЛОГ НА HUSL

Найти количество N-значных чисел, у которых сумма цифр равна их произведению (оптимизировать код)

Ответы (2 шт):