Count numbers with constrained digits using tight/loose states
Traverse digits most-significant to least with a 'tight' flag and memoize (pos, tight, state...).
Use for counting numbers ≤ N with properties (e.g., no consecutive ones, digit sums).
Pick digits up to the bound when tight; memoize (i, tight, state...) and handle leading zeros to avoid double counts.
# String Algorithms Template (KMP)
def kmp_search(text, pattern):
if not pattern: return 0
lps=[0]*len(pattern)
j=0
for i in range(1,len(pattern)):
while j>0 and pattern[i]!=pattern[j]: j=lps[j-1]
if pattern[i]==pattern[j]: j+=1; lps[i]=j
j=0
for i,ch in enumerate(text):
while j>0 and ch!=pattern[j]: j=lps[j-1]
if ch==pattern[j]: j+=1
if j==len(pattern): return i-j+1
return -1Constrain next digit when tight
from functools import lru_cache
def count_no_consec_ones(n):
s = bin(n)[2:]
@lru_cache(None)
def dp(i, tight, prev1):
if i == len(s): return 1
up = int(s[i]) if tight else 1
total = 0
for d in range(up + 1):
if prev1 and d == 1: continue
total += dp(i+1, tight and d==up, d==1)
return total
return dp(0, True, False)Carry state like prev digit/sum
from functools import lru_cache
def count_digits_sum_leq(n, target):
s=str(n)
@lru_cache(None)
def dp(i, tight, sum_):
if i==len(s): return 1 if sum_<=target else 0
up = int(s[i]) if tight else 9
total=0
for d in range(up+1):
total += dp(i+1, tight and d==up, sum_+d)
return total
return dp(0, True, 0)