Вариант для bigint, который быстро считает результат даже для громадных чисел:
// вспомогательная функция
function countDig(n, pow, pow10, pow9) {
const dig = n / pow10;
const count = dig < 6n ? dig : dig - 1n;
return count * pow9 + (dig === 5n || pow < 1n ? 0n : countDig(n % pow10, pow - 1n, pow10 / 10n, pow9 / 9n));
}
// количество беспятёрочников на отрезке [0...n-1]
function countWithout5(n) {
let pow = 0n, pow10 = 1n;
while (pow10 * 10n <= n) {
pow++;
pow10 = pow10 * 10n;
}
return countDig(n, pow, pow10, 9n ** pow);
}
function count(min, max) {
if (min > max) {
return 0n;
}
if (min >= 0n) {
return countWithout5(max + 1n) - countWithout5(min);
}
if (max <= 0n) {
return countWithout5(1n - min) - countWithout5(-max);
}
return countWithout5(max + 1n) + countWithout5(1n - min) - 1n;
}
count(4n, 17n); // 12n
count(-3455534n, 1731643265265475472546254726454363145657453757347547n);
// результат 7912695757329425999049503116097171379949505558054n
в решении используется тот факт, что на отрезке от 0 до (10^k)-1 включительно (то есть для неотрицательных чисел длиной не более k) существует всего 9^k чисел, не содержащих пятерку. Почему столько? Это числа длиной k, если слева дозаполнить нулями, и на каждом разряде возможно 9 разных цифр, итого 9^k вариантов.
