count '9's from 1 to n

Question

Решаю задачу на codewars.com
Задача: count '9's from 1 to n
Моё решение:

def count_nines(n):
    list1 = str(list(range(1,n+1)))
    count = 0
    nine = ['9']
    for i in list1:
        if i in nine:
            count = count + 1
    return count

Ошибка: MemoryError если через сайт запускать, в моем IDE все работает как надо, правда медленно при больших числах
Еще из ограничений самой платформы codewars:

функция должна принимать только 1 аргумент
выполняться за время не более 12000 ms

Answer 1

Можно так сделать:

def digit_count(digit, start, end):
    count = 0
    for number in range(start, end):
        while number:
            count += (number%10 == digit)
            number //= 10
    return count

Если можно использовать модули, то можно сделать так:

def digit_count(digit, start, end):
    @functools.lru_cache()
    def f(digit, number, first_call=False):
        if number==0 and first_call==False:
            return 0
        return (number%10==digit) + f(digit, number//10)
    count = 0
    for number in range(start, end):
        count += f(digit, number, first_call=True)
    return count

Answer 2

x = 0
for i in range(1, int(input()) + 1):
    x += str(i).count('9')
print(x)

Answer 3

NB: Я везде ниже немного занижаю оценки, чтобы проще было объяснять.

Исходное решение требует O(n) памяти. Сперва строится список чисел из n чисел. Затем строится строка в которой O(n) символов. Всё это может не поместится в память при больших n. Поправить можно сравнительно просто:

def count_nines(n):
    return sum(str(i).count('9') for i in range(1, n + 1))

Это код использует фиксированное количество памяти, но всё ещё работает за линейное время (то есть медленно), потому что перебирает все числа от единицы до n.

Быстрое решение

Обозначим f(n) - число девяток в десятичных записях всех чисел [0, n). Обратите внимание, что n исключена.

Обозначим g(n) - число девяток в десятичной записи числа n.

Как связаны f(n) и f(10 * n)?

f(10 * n) = 10 * f(n) + n

Чтобы понять почему это так выпишем все числа [0, 10 * n) в таблицу. Вот её кусочек (последний разряд отделен пробелом только для читабельности):

...
987 0   # '987' входил в f(n) один раз
987 1   # он же входит в f(10 * n) десять раз
987 2   # таким образом первое слагаемое 10 * f(n)
987 3   # перечисляет все девятки со второго разряда и выше
987 4
987 5
987 6
987 7
987 8
987 9   # девяток в первом разряде ровно n штук  
...     # это второе слагаемое

Усложним формулу. Появилась добавка d. Лишние числа добавляем в сумму в ручном режиме:

f(10 * n + d) = 10 * f(n) + n + sum(g(10 * n + i), 0 <= i < d)

Используя эту формулу можно решить задачу так:

def g(n):
    return str(n).count('9')


def f(n):
    if n == 0:
        return 0
    d = n % 10
    m = n // 10
    return 10 * f(m) + m + sum(g(10 * m + i) for i in range(d))


def count_nines(n):
    return f(n + 1)

Время работы этой программы пропорционально количеству разрядов в числе n.

БЛОГ НА HUSL

count '9's from 1 to n

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

Быстрое решение