0

Кратко об условии и ограничениях,меня не интересует простейшая реализация,но если изменить решения с сайта https://www.geeksforgeeks.org/count-numbers-having-0-as-a-digit/ то буду благодарен)

Дано число n,надо найти все такие числа от 1 до n что имеют цифру d(1..9) в своей записи.

Тест:
100 1 

Числа что имеють единицу - (1,10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91,100)

Вывод
20

Ограничения:
1<=n<=10^18
1<=d<=9

Час: 1 секунда
8
  • а чем простейшая реализация от иной отличается? 15 окт 2018 в 12:42
  • Сложность там цикл 1 до n и еще по длине каждого елемента не зайдёт в лимит 1 секунду. 15 окт 2018 в 12:47
  • 2
    в вопросе ничего нет про лимит 15 окт 2018 в 12:51
  • 1
    если коротко: t = 100, r = 1 и len(filter(lambda x: x>0, map(lambda x: (str(x)).count(str(r)), range(1, t + 1)))), то 20. ` 15 окт 2018 в 12:52
  • или сразу t = 100, r = 1 и len(filter(lambda x: (str(x)).count(str(r)) >0, range(1, t + 1))) python 2.7 15 окт 2018 в 12:58

2 ответа 2

0

Всё просто) на самом деле нужно считать число тех чисел которые не содержат данной. Так как d всегда не 0, для простоты добавим ведущие 0.

Пусть мы ищем ответ для числа a. Перебираем первую цифру. Для всех цифр меньше (строго!) a[0] (старшей цифры) и если она не равна d добавим к ответу 9^(X-1). Теперь фиксируем первую цифру в a[0] (если не равно d), убираем первую фиру из числа и спускаемся на уровень ниже.

Осталось только вычесть.

Пример

12345 3.

Пошаговое.

1. 9^4 = 6561
2. 2*9^3 = 1458
3. 3*9^2 = 243
Дальше не надо, т.к. d = 3.

Итого ответ 12345 - (6561+1458+243-1) = 4084.

-1 надо т.к. способ считает 0 числом. Нужно его вычесть отдельно.

Лобовые циклы слишком медленные.

P.S. при d = 0 формулы меняются.

8
  • 1
    Несомненно, у Вас в голове решение сложилось (это видно по ключевым идеям). Но то, что написано - "сумбур вместо музыки" (c)
    – MBo
    15 окт 2018 в 15:16
  • @MBo все ключевые идеи есть) дальше думаю самому интересно будет подумать тем, кто с таким не сталкивался. Задача явно учебная, поэтому детальные ответы как по мне не очень хорошо. Но вы можете написать свой или отредактировать этот.
    – pavel
    15 окт 2018 в 15:23
  • Я писал такую же програмку,если зайдёт ваше решение то одобрю) 15 окт 2018 в 15:33
  • А что если дано число 99999 при цифре 3?Как ваш алгоритм будёт работать опишите подробнее 15 окт 2018 в 15:47
  • @AndriyOleksievets 1 шаг. от 0 до 8 без 3. 8*9^4 = 52488. 9 фиксированно. Дальше по анологии. 8*9^3, 8*9^2, 8*9, 8. Сумма 59048. Ответ 40952.
    – pavel
    15 окт 2018 в 17:32
0

Верная идея у Eugene Dennis, но не нужно никаких фильтров. простой list comprehension:

rng, num=100, 1
len([x for x in range(1, rng + 1) if (str(x)).count(str(num))>0 ])

Output:

20
2
  • Вы хотите сказать, что О(n) алгоритм успеет за 1 секунду просчитать до 10^18? Деталей не скажу, но это О(log n), т.е. нужно пробегать 0..9 по каждому разряду и для чисел 1..100 это займет всего 2*10+1 итерацию. Для 10^18 соответственно, всего 180 итераций.
    – Lecron
    15 окт 2018 в 15:17
  • Я просил никакого решения в лоб,не одобряю так как сам накатаю такой алгоритм за 5 секунд. 15 окт 2018 в 15:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.