solve(pos,tight,started,summary) counts valid completions. The digit ranges from 0 to digits[pos] if tight, otherwise base-1; next_tight is tight and equality with the bound digit. Answer [L,R] by F(R)-F(L-1).
Recognition signals
Count integers in [0,N] or [L,R].
The property updates digit by digit, such as sum, remainder, frequency, or adjacency.
N is too large for enumerating every integer.
Many numbers share equivalent high-prefix states.
A tight flag can express the upper-bound restriction.
False friends
Signal
Why it is different
Inspecting one given number
A simple digit loop suffices; no state reuse is needed.
A property requiring arbitrary full history
If history cannot be compressed into a small summary, state size explodes.
No bound and a tiny fixed length
Direct combinatorics or a simple recurrence may be clearer.
Core invariant
All prefixes sharing pos/tight/started/summary have exactly the same valid suffix set; tight precisely records whether the prefix still equals the upper-bound prefix.
State, transition, and processing order
Item
Definition
State
Position, tight flag, started flag, and the minimal property summary such as remainder, sum, count, or previous digit.
Transition
Enumerate each legal digit, update started and summary, and keep tight only when the old state was tight and the chosen digit equals the bound digit.
Frontier / order
DFS or iterative layers from most significant to least; cache either all states including tight or only the reusable non-tight states.
Python skeleton
from functools import lru_cache
def count_digit_sum_at_most(n, target):
if n < 0: return 0
digits = list(map(int, str(n)))
@lru_cache(None)
def dfs(pos, tight, total):
if total > target: return 0
if pos == len(digits): return int(total == target)
limit = digits[pos] if tight else 9
ans = 0
for d in range(limit + 1):
ans += dfs(pos + 1, tight and d == limit, total + d)
return ans
return dfs(0, True, 0)
Correctness sketch
Every integer from 0 through N has one fixed-length leading-zero digit path.
The tight update excludes exactly the prefixes that first exceed N while retaining every bounded path.
The summary updates deterministically and the terminal test accepts exactly the property; distinct paths represent distinct integers.
Complexity
Time
Space
Parameters
O(D·B·|Summary|·2), up to transition constants
O(D·|Summary|·2)
D is digit count, B the base, and Summary the property-state domain.
Edge cases
n<0 for L-1
whether zero counts
leading zeros and started
including N itself
summary pruning
non-decimal bases
Error patterns
Pattern
Why it fails / fix
Updating tight against the wrong value
Use old_tight and equality with the actual bound digit at pos; do not improvise from a reused limit.
Treating leading zeros as real digits
Occurrence and adjacency properties need started to distinguish padding.
Mishandling L=0 in range subtraction
Define F(n)=0 for n<0, then always use F(R)-F(L-1).
Omitting influential data from the cache key
Every quantity that changes legal suffixes belongs in state; bound digits must stay fixed within one call.
Selection and exclusion rules
Convert an interval query into prefix count F(N).
Prove that the property has a small digit-updatable summary.
Specify whether padding zeros are part of the representation.