Наихудший делитель

Question

Будем считать, что число а лучше числа b, если сумма цифр числа а больше суммы цифр числа b, а в случае равенства сумм, если число а меньше числа b.
Дано число n. Найдите такой его делитель d, что любой другой делитель с числа n лучше, чем d.
Пример:
Ввод: 10
Вывод: 10
Ввод: 239
Вывод: 1

Я понял, что здесь нужно считать нули. Вот мой код:
a=input()
b=0
for i in range(len(a)):
    if int(a[i])==0:
        b+=1
if int(a)<10:
    print(a)
elif b==0:
    print(1)
else:
    print(a)

Не проходит дальше 4-го теста..

n1tr0xs · Answer

Вот так можно:
def main(n):
    for i in range(len(str(n))):
        k = 10**i
        if not n % k:
            worst = k
    return worst

n = int(input())
print(main(n))

Zhihar · Answer

Примерный алгоритм
# функция определения суммы цифр числа
def sum_digits(a):
    res = 0

while a != 0:
        res += a % 10
        a /= 10

return res

# функция определения является ли число a лучше числа b
def is_best(a, b):
    sum_a = sum_digits(a)
    sum_b = sum_digits(b)

if sum_a > sum_b:
        return True

if sum_a == sum_b:
        return a < b

return False

# основной функционал
n = int(input())

worst = 1

for value in range(2, n + 1):
    # рассматривать только делители числа n
    if n % value == 0:
        # найти худшее число
        if not is_best(value, worst):
            worst = value

print(worst)

Zhihar · Answer

вообще код какой-то кривоватый
ваш код умеет выводить только или 1 или само число, а в задаче вопрос про делители числа, т.е. ваш ответ никаких иных делителей принципиально не выводит
поэтому и тест валится - ведь в тесте 4 скорее всего результат - один из делителей (для 10 например 2 или 5)
Почему бы вам не переписать алгоритм так (в лоб):

найти все делители числа n и записать их в список

создать функцию проверки на "лучшесть" из 2 чисел

сделать проход по всем делителям (т.е. будет выполнено n^2 проходов) и сравнить с остальными делителями

P.S.
предложенный алгоритм имел сложность O(n^2), но это я погорячился :)
лучше подойдет такой алгоритм:

идем по числу m от 2 до n и определяем, что число является делителем n
сравниваем делитель m с предыдущем делителем m_prev через функцию "лучшести" и если число лучше предыдущего, то записываем его в m_prev

в итоге сложность такой задачи будет O(n), что гораздо лучше
и никаких лишних списков заполнять не надо
ну и цикл от 2, потому что m_prev = 1
и кстати тогда проверку надо на то, что пользователь ввел 1 и тогда выдать сразу ответ - 1

Наихудший делитель

3 Answers

Add your own answers!

Ask a Question