How many integers in [0, n] do not contain the digit 4? How many have digit sum k? n is up to 10^{18} — you cannot loop. You walk the decimal representation.
State: pos (which digit you are filling), tight (whether the prefix still matches n, so the next digit is capped), and the property so far (seen a 4, digit sum, last digit, …). If tight is false, remaining digits are free 0..9.
count(r) - count(l-1) gives a range. CSES Counting Numbers. This is the usual CF 1800 'how many numbers' problem.
function countWithoutFour(n) {
if (n < 0) return 0;
const digits = String(n).split("").map(Number);
const memo = new Map();
function dp(pos, tight, started) {
if (pos === digits.length) return 1;
const key = pos + "," + tight + "," + started;
if (memo.has(key)) return memo.get(key);
const cap = tight ? digits[pos] : 9;
let ways = 0;
for (let d = 0; d <= cap; d++) {
if (d === 4) continue;
ways += dp(pos + 1, tight && d === cap, started || d > 0);
}
memo.set(key, ways);
return ways;
}
return dp(0, true, false);
}Checks 0/2