935. Knight Dialer

Medium

1.9K

382

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**). The possible movements of chess knight are shown in this diagaram:

A chess knight can move as indicated in the chess diagram below:

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

**Example 1:**

Input:n = 1Output:10Explanation: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 = 2Output:20Explanation: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 = 3131Output:136006598Explanation:Please take care of the mod.

**Constraints:**

`1 <= n <= 5000`

Accepted

98.6K

Submissions

195.3K

Acceptance Rate

50.5%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved