Knight Dialer
Medium · Dynamic Programming · Dynamic Programming
Problem
A chess knight stands on a phone keypad laid out as
It may stand only on the digit keys. A knight moves two keys in one direction and then one key at a right angle (an L shape).
Given n, return how many distinct phone numbers of length n you can dial: place the knight on any digit to dial the first digit, then make n - 1 valid knight jumps, dialing each digit you land on. Return the answer modulo 10^9 + 7.
Examples
Input: n = 3 Output: 46
Adding up the two-jump walks from every starting digit gives 46 numbers.
Input: n = 4 Output: 104
Extending each of those walks by one more legal jump gives 104 numbers.
Input: n = 31 Output: 352313197
The count passes 10^9 + 7, so the answer is reduced modulo it.
Constraints
- 1 <= n <= 5000
Approaches
- Counts per ending digit, one jump at a time — time O(n), space O(1)
Follow-up
For n up to 10^18 only the matrix power works: about 60 squarings of a 10 × 10 matrix. The symmetry of the keypad also shrinks the state: digits 1, 3, 7 and 9 behave alike, as do 2 and 8, and 4 and 6, so four counts are enough. Digit 5 matters only for n = 1.
Related problems
Start free on Cariara · Coding problems · System design studio
