Skip to main content

Counting Numbers (Digit DP)

Learn Counting Numbers (Digit DP) (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Counting Numbers in [0, N] With a Property, Digit by Digit Digit DP answers questions like "how many numbers up to N contain no digit greater than 5" WITHOUT iterating every number individually (impossible for huge N). It builds the number ONE DIGIT AT A TIME, tracking whether the prefix built so far is still "tight" (equal to N's prefix, constraining future digit choices) or already "free" (strictly less, so any digit is allowed).

More lessons in Dynamic Programming