Количество целых чисел в заданном диапазоне, у которых последние K цифр равны

Учитывая диапазон от L до R и целое число K , задача состоит в том, чтобы подсчитать количество целых чисел в заданном диапазоне, у которых последние K цифр равны.

Пример:

Input: L = 49, R = 101, K=2
Output: 6
Explanation: There are 6 possible integers t.e., 55, 66, 77, 88, 99 and 100 such that their last K(i.e., 2) digits are equal.

Input: L = 10, R = 20, K=2
Output: 1

Эффективный подход: можно заметить, что количество целых чисел i в диапазоне от 1 до X , у которых последние K цифр равны целому числу z (т. е. i % 10 ^K = z), равно (X – z)/10 ^K + 1 . . Используя это наблюдение, вышеуказанная проблема может быть решена с помощью следующих шагов:

1. Предположим , что intCount(X, K) представляет количество целых чисел от 1 до X , у которых последние K цифр равны.
2. Чтобы вычислить intCount(X, K) , выполните итерацию по всем возможностям z , имеющим K цифр (т.е. {00…0, 11…1, 22…2, 33…3, 44…4, …., 99…9 } ) в формуле (X – z)/10 ^K +1 и сохранить их сумму, которая и является искомой величиной.
3. Следовательно, количество целых чисел в диапазоне от L до R можно получить как intCount(R, K) – intCount(L-1, K) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log K)
Космическая сложность: O(1)