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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Knight Dialer and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →