Найти минимальное число, произведение цифр которого равно N

Question

Найти минимальное число, произведение цифр которого равно N

Рейтинг: 3Ответов: 3Опубликовано: 14.05.2023

я писала код по задаче

Дано натуральное число N Найдите минимальное число большее 10, произведение цифр которого в точности равно N

Но на некоторых тестах (которые, к сожалению, неизвестны) моя программа работает слишком долго.


n=int(input()) 
ans="No solution"
if n==0:
    print(10)
elif n<10:
    print(int("1"+str(n)))
else:
    for i in range(int("9"*n)):
        i=str(i) 
        a=1 
        for j in range(len(i)):
            a*=int(i[j])
        if n==a:
            ans=i 
            break
    print(ans)

Я не знаю, что не так... Помогите пожалуйста разобраться!

python

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

Сделал небольшую функцию, которая решает эту задачу (если вводимое число кратно какому-либо простому числу (кроме 1,2,3,5,7)-функция выведет это простое число вместо ответа):

n = int(input())
def min_mult_num(n):
    if n == 0:
        return 10
    elif n < 10:
        return int('1' + str(n))
    else:
        n_mute = n
        list_help = []
        final_num = []
        for i in range(2,10):
            list_help.append(i)
        list_help = list_help[::-1]
        while len(str(n_mute)) > 1:
            for i in list_help:
                if n_mute%i == 0:
                    final_num.append(i)
                    n_mute = int(n_mute / i)
                    break
            else:
                return (f"Мы столкнулись с простым числом {n_mute}")
        final_num.append(n_mute)
        final_num = final_num[::-1]
        f = int(''.join((str(i) for i in final_num)))
        return f

min_mult_num(n)

если надо что то объяснить по логике функции, то напишите в комментах к этому ответу, постараюсь объяснить

Answer 2

▲ 1

Предлагаю небольшую рационализацию внутреннего цикла - досрочное завершение, если ответ явно не получится уже и крутить цикл дальше бесполезно:

        for j in range(len(i)):
            a*=int(i[j])
            if a == 0 or a > n:
                break

Хотя нужно проверять, даст ли это экономию. В принципе, должно дать, потому что операции сравнения чисел очень дешёвые, а вот парсинг строки в число - очень дорогая операция. Умножение не сильно дорогое.

Но вообще явно задачу нужно решать в обратную сторону - с разложения на множители. Так должно быть гораздо быстрее.

Answer 3

▲ 0

В вашем решении есть несколько недочётов.

Условие if n == 0: не нужно. n - натуральное, нулём быть не может.
Очень долго ждать ответа если решения нет. Минимальное n без ответа - 11. Вы запускаете цикл из 99_999_999_999 итераций. 100 миллиардов - много. Правило большого пальца: современный компьютер делает порядка миллиарда элементарных операций в секунду. 100 секунд можно было бы подождать, но у нас и операции не элементарные. Быстрая прикидка показывает что миллион итераций ваша программа делает за три секунды. А требуется в 100_000 раз больше.
Это не ваш недочёт, а странность в условии задачи: почему ответ должен быть больше десяти? Не понятно. Я пока опущу это условие - буду искать минимальное число с нужным произведением цифр.

Перебор кандидатов напрашивается, но не всегда простейшее решение - лучшее. Разберем примеры для n = 18. Если задача имеет решение, то цифры решения должны делить 18. Подходят 2, 3, 6, 9. Из них можно скомбинировать такие ответы: 18 = 2 * 3 * 3 = 2 * 9 = 3 * 6. С точностью до порядка множителей других комбинаций нет.

Разберёмся с порядком: 2 * 9 = 9 * 2. Из равенства следуют два решения: 29 и 92. Нам нужно меньшее: 29. Вывод: цифры в числе должны не убывать. Если они в каком-то месте убывают, пару цифр можно поменять местами и получить меньшее число с тем же произведением.

Второе наблюдение: чем меньше цифр, тем меньше число: 2 * 9 = 2 * 3 * 3. 29 < 233.

Тогда алгоритм такой: делим n на 9 пока делится и выписываем девятки справа налево в разряды числа. Затем переходим к 8 - выписываем восьмёрки пока делится. Продолжаем пока не дойдём до 2. Когда все двойки выписаны, проверяем что n = 1. Если нет, в n есть множители которые не могут быть цифрами - ответа нет.

Этот алгоритм строит самое короткое число (второе наблюдение) и цифры в нём не убывают (первое наблюдение).

Если в ответе получилось число из одной цифры, добавляем к нему спереди единицу, чтобы соответствовать "странному" условию из задачи:

n = int(input()) 
answer = []
for d in range(9, 1, -1):
    while n % d == 0:
        n //= d
        answer.append(str(d))
if n > 1: # n не является произведением чисел от 2 до 9
    print('No solution')
else:
    if len(answer) == 0: # это бывает если n = 1
        answer.append('1')
    if len(answer) == 1: # это бывает если n < 10
        answer.append('1')
    print(''.join(reversed(answer)))

$ echo 1 | python digits.py
11

$ echo 2 | python digits.py
12

$ echo 9 | python digits.py
19

$ echo 10 | python digits.py
25

$ echo 11 | python digits.py
No solution

$ echo 50 | python digits.py
255

$ echo 1000000000000 | python digits.py
5555555555558888

Найти минимальное число, произведение цифр которого равно N

Ответы