861. Knight's Dial
A museum kiosk has a classic phone keypad: 1 2 3 on top, 4 5 6 and 7 8 9 in the middle, and 0 alone in the centre of the bottom row (the other two bottom cells are empty). A visitor puts a finger on any digit key, then repeatedly moves it like a chess knight: two cells in one direction and one cell perpendicular, always landing on a digit key. Each landing key is typed.
Return how many different digit strings of length n can be typed (the starting key counts as the first digit), modulo 1_000_000_007 (10^9 + 7). For n = 1 every one of the ten keys is a valid start.
Example 1
- Input:
- n = 4
- Output:
- 104
- Explanation:
Exactly 104 different digit strings of length 4 can be dialled when each next key is a chess-knight hop from the previous key.
Example 2
- Input:
- n = 5
- Output:
- 240
- Explanation:
Extending every length-4 dialling by one knight hop in all possible ways produces 240 strings of length 5.
Constraints
- 1 ≤ n ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)