Mid/SeniorDynamic Programming
Knight Dialer
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, where the knight can only stand on a numeric cell.
Given an integer n, return how many distinct phone numbers of length n can be dialed.
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.
Example 1
Input
n = 1Output
10We 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 = 2Output
20All the valid numbers we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94].
Constraints
- 1 <= n <= 5000
Asked at 7 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.