Skip to main content

935. Knight Dialer

medium

Count distinct phone numbers of length n a chess knight can dial on a phone keypad. A 10-state finite-automaton DP that rolls forward digit by digit.

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

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 knight-move adjacency for each of the 10 digits on the keypad.

Hint 2

Let dp[d] = number of length-k numbers ending at digit d. Update dp[d] for length k+1 by summing dp over neighbors of d.

Hint 3

Start with dp[d] = 1 for every d at length 1. After n-1 transitions sum dp.

Solution approach

Reveal approach

Precompute the knight's adjacency list on the keypad: 1 -> {6, 8}; 2 -> {7, 9}; 3 -> {4, 8}; 4 -> {0, 3, 9}; 6 -> {0, 1, 7}; 7 -> {2, 6}; 8 -> {1, 3}; 9 -> {2, 4}; 0 -> {4, 6}; 5 -> {}. Maintain dp[0..9] where dp[d] is the number of length-k numbers ending at digit d. Initialize dp[d] = 1 for every d at length 1. For each step from 2 to n compute next[d] = sum of dp[m] for every m that can knight-jump to d, modulo 10^9 + 7. Replace dp with next. Return sum(dp) modulo M. O(n) time with a constant adjacency factor, O(1) space (10 slots).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine
  • matrix-exponentiation

Related problems

Asked at

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

  • Amazon
  • Google

More DP 1D practice problems

See all DP 1D problems →