Skip to main content

935. Knight Dialer

medium

Count distinct n-digit numbers a chess knight can dial on a phone keypad. 2D DP keyed on (steps-left, current key) — classic transition table with the keypad's adjacency baked in.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell). Given an integer n, return how many distinct phone numbers of length n we can dial. You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps. As the answer may be very large, return the answer modulo 10^9 + 7.

Constraints

  • 1 <= n <= 5000

Examples

Example 1

Input
n = 1
Output
10

Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2

Input
n = 2
Output
20

Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94].

Example 3

Input
n = 3131
Output
136006598

Explanation: Please take care of the mod.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Precompute the adjacency for each numeric key: 1 -> {6, 8}, 2 -> {7, 9}, 3 -> {4, 8}, etc.

Hint 2

dp[step][key] = number of length-(step+1) sequences ending at key. Recurrence: dp[step][key] = sum of dp[step-1][neighbor] for every neighbor of key.

Hint 3

Base: dp[0][key] = 1 for every numeric key.

Hint 4

Apply mod after each addition. Space optimization: keep only the previous step's row — 10 entries.

Solution approach

Reveal approach

Precompute the knight-jump adjacency for every numeric key on the keypad (1-9 and 0). Maintain a length-10 array dp where dp[k] is the number of valid sequences of the current length ending at key k. Initialize dp[k] = 1 for every key (the length-1 base case). Repeat n-1 times: build a new array next where next[k] = sum of dp[neighbor] for every neighbor of k, taken mod 10^9 + 7. Replace dp with next. After n-1 iterations, the answer is the sum of dp[k] over all 10 keys, mod 10^9 + 7. The transition is a fixed sparse matrix-vector product; for very large n you can apply matrix exponentiation to push the time below O(n).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Apple
  • Microsoft

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →