V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Digit DP

Count valid numbers by scanning upper-bound digits with tight and free suffix states.

Core idea

Scan the upper bound from most significant digit to least. A tight prefix may not exceed the bound digit; choosing a smaller digit releases every later position from that limit.

Read the visualization

The table separates free branches from the single tight path. Each row shows how many valid suffixes follow a smaller choice and whether matching the bound digit survives.

at digitavailable valuessuffix 9^ksubtotal
hundreds digit 2
tens digit 4
ones digit 5
total

Split the upper bound into digits and begin in the tight prefix state.

1function countNoBan(n: number, ban: number): number {
2 const ds = [...String(n)].map(Number); // up init number digit (init digit init)
3 let total = 0;
4 let tight = true; // init tight to the upper bound init
5 for (let i = 0; i < ds.length && tight; i++) {
6 const free = ds.length - i - 1; // suffix init digit count
7 let cnt = 0;
8 for (let x = 0; x < ds[i]; x++) // current digit free less than up free digit free number
9 if (x !== ban) cnt++;
10 total += cnt * 9 ** free; // free count free suffix 9^free free
11 if (ds[i] === ban) tight = false; // up tight digit tight forbidden digit: broken
12 }
13 if (tight) total += 1; // N sum
14 return total - 1; // done 0
15}
N / forbidden245 / digit 4
tight✓( start step tight to the upper bound)
1 / 8

Complexity and tradeoffs

Time: O(d × states × radix). Space: O(d × states). Memoization collapses all prefixes that share position, constraint state, and tightness.

Invariant: Every counted prefix is either exactly equal to the bound prefix or already smaller, and the remaining state captures all constraints needed for its suffix.

Where it fits

Digit DP counts bounded integers with forbidden digits, digit sums, automaton constraints, and modular properties without enumerating the range.