📜 WAYPOINT LESSON
Free-State Transitions
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 158 of 281
A free suffix of length k contributes a fixed count per state — precompute one transition table and reuse it for every query.
The free table
For digit-sum problems the free state is just the running sum modulo m. One free digit sends remainder r to (r + d) % 3 with multiplicity (4, 3, 3) — digits {0,3,6,9}, {1,4,7}, {2,5,8}. Squaring the one-digit table gives two digits; iterating gives any length. The tight walk then queries the table once per position: O(19) table lookups per number.