Подсчет вхождений цифр

Question

Эта проблема действительно смущает меня;нам даны два целых числа A , B , мы хотим подсчитать вхождения цифр в диапазоне [A, B] .Я думал, что если бы мы могли посчитать количество вхождений цифр в диапазоне [0, A] и [0, B] , то все остальное тривиально.Итак, как я могу подсчитать количество вхождений цифр в диапазоне [0, x] ?Это не домашняя работа, это на самом деле проблема от SPOJ.Наивный подход не сработает, поскольку A и B могут достигать 10 ^ 9. Вот несколько примеров:

Ввод:

1 10

Вывод:

1 2 1 1 1 1 1 1 1 1

Ввод:

44 497

Вывод:

85 185 185 185 190 96 96 96 95 93

Answer 1

Сначала я бы попробовал метод грубой силы, чтобы что-то заработало. Посмотрите на каждое число, переберите каждый символ в строковом представлении этого числа и т. Д.

Однако есть более простой способ.

• В интервале [0,9] 3 появляется 1 раз
• В интервале [0,99] 3 появляется 10 раз в первой цифре и 10 раз во второй цифре
• В интервале [0,999], 3 появляется 100 раз в первой цифре, 100 раз во второй цифре и 100 раз в третьей цифре.

Вы можете обобщить это и с небольшим усилием придумать формулу для того, сколько из определенной цифры (0 - возможный особый случай) появится в определенном диапазоне Вам не нужно на самом деле проходить каждый номер.

Answer 2

Вольфрам Альфа - твой друг (по крайней мере, по номеру около 21 * 10 ^ 4):

Input:

44 497

Output:

85 185 185 185 190 96 96 96 95 93 

Попробуй меня

Результат:

{85, 185, 185, 185, 188, 96, 96, 96, 95, 93}

Answer 3

С такими проблемами часто полезно начать с медленной и уродливой реализации, прежде чем понять, как это сделать правильно и быстро.Вы можете кое-что узнать о структуре проблемы, и вы можете использовать медленную реализацию, чтобы проверить правильность быстрой.

Например, в Python вы можете написать медленную версию, подобную этой (это необязательно лучший способ сделать это, но это один из самых коротких ...)

>>> A, B = 1, 100
>>> from collections import Counter
>>> Counter(''.join(map(str, range(A, B + 1))))
Counter({'1': 21, '3': 20, '2': 20, '5': 20, '4': 20,
         '7': 20, '6': 20, '9': 20, '8': 20, '0': 11})