FunctionRacerProblemsRace

Knight on the Keypad

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

A phone keypad has the rows 1 2 3, 4 5 6 and 7 8 9, plus a bottom row with only 0, under the 8. A chess knight starts on any key and dials it, then makes length - 1 knight moves (two keys in a straight line, then one key to the side), dialing every key it lands on. It may never use a key listed in broken, not even as its first key.

Return how many different digit strings of length digits the knight can dial, modulo 1,000,000,007.

Example 1

length 2
broken []
returns 20

Every key except 5 has two or three knight moves, and together they make 20 two-digit strings, such as 16, 40 and 94.

Example 2

length 3
broken [1,3,7,9]
returns 6

Only 0, 4 and 6 still connect: 4 and 6 jump to 0, and 0 jumps to 4 or 6. That gives 040, 060, 404, 406, 604 and 606.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems