# 27.11.2023 [935. Knight Dialer]
Count of dialer `n`-length numbers formed by pressing in a chess Knight's moves
27.11.2023
935. Knight Dialer medium
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/418
Problem TLDR
Count of dialer n
-length numbers formed by pressing in a chess Knight’s moves
Intuition
We can search with Depth-First Search for every position and count every path that has `n`
digits in it.
The result will only depend on a previous number and count of the remaining moves, so can be cached.
Approach
Let’s write a separate paths
map: current digit to next possible.
Complexity
Time complexity:
O(n),10
digits is a constant valueSpace complexity:
O(n)
Code
val dp = mutableMapOf<Pair<Int, Int>, Int>()
val paths = mapOf(
-1 to (0..9).toList(),
0 to listOf(4, 6),
1 to listOf(6, 8),
2 to listOf(7, 9),
3 to listOf(4, 8),
4 to listOf(3, 9, 0),
5 to listOf(),
6 to listOf(1, 7, 0),
7 to listOf(2, 6),
8 to listOf(1, 3),
9 to listOf(2, 4))
fun knightDialer(pos: Int, prev: Int = -1): Int =
if (pos == 0) 1 else dp.getOrPut(pos to prev) {
paths[prev]!!.map { knightDialer(pos - 1, it) }
.fold(0) { r, t -> (r + t) % 1_000_000_007 }
}