Last Updated: 4 Dec, 2021
Knight Dialer
Moderate
Asked in companies
You are given a number pad as shown in the figure below, and you also have a ‘knight’ piece from chess. Your task is to determine how many different ‘N’ digit numbers can be formed by placing the ‘knight’ anywhere on the number pad and moving the ‘knight’ according to the rules of chess.
Note:
Return the solution modulo 10^9 + 7.
For example:
You are given ‘N’ = 2, all the unique 2 digit numbers formed moving the knight on the number pad are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]. Hence the answer is 20.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.
The first and the only line of each test case contains a single integer ‘N’.
Output Format:
Print a single integer for each test case, representing the number of distinct numbers formed by moving the knight.
Print a separate line for each test case.
Constraints
1 <= T <= 10
1 <= N <= 10^3
Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we will visit each position in the number pad and count the number of distinct numbers that can be dialled. We will make a map of all the places to be visited from a given number.
We create a recursive function helper(currPos, nextPositions, digitsRem), currPos is the current key on the number pad, nextPositions is the map of the next positions from any key, and digitsRem is the number of digits left to form the number.
Algorithm:
- In the helper(currPos, nextPositions, digitsRem),
- If digitRem is equal to 1, return 1
- Set ans as 0
- Iterate nextPos through nextPositions[currentPos]
- Add helper(nextPos, nextPositions, digitsRem - 1) to ans.
- Return ans modulo 10^9 + 7
- In given function
- If n is equal to 1, return 10
- Set ans as 0
- Create a map nextPositions with integer key and a list as value, corresponding to the next position of the knight from the key.
- Iterate i from 0 to 9
- Add helper(i, nextPositions, n) to ans.
- Return ans modulo 10^9 + 7
This approach is similar to the previous approach, but we will make a cache to store the already calculate solutions of the current position and the number of digits remaining.
We create a recursive function helper(currPos, nextPositions, digitsRem, cache), currPos is the current key on the number pad, nextPositions is the map of the next positions from any key, digitsRem is the number of digits left to form the number and cache is the cache that stores previously calculated answers.
Algorithm:
- In the helper(currPos, nextPositions, digitsRem, cache),
- If digitRem is equal to 1, return 1
- If cache[currentPos][digitsRem] is not equal to -1, return it.
- Set ans as 0
- Iterate nextPos through nextPositions[currentPos]
- Add helper(nextPos, nextPositions, digitsRem - 1,cache) to ans.
- Set cache[currentPos][digitsRem] as ans modulo 10^9 + 7
- Return ans modulo 10^9 + 7
- In given function
- If n is equal to 1, return 10
- Set ans as 0
- Create a 2D matrix of n X 10 size, with all values as -1, cache.
- Create a map nextPositions with integer key and a list as value, corresponding to the next position of the knight from the key.
- Iterate i from 0 to 9
- Add helper(i, nextPositions, n, cache) to ans.
- Return ans modulo 10^9 + 7
In this approach, we can see that the number of ways to reach a given position in the number pad, is the sum of the number of ways to reach all the positions from which we can come to our current position. For example, the number of ways to reach 1 is the sum of the number of ways to reach 6 and 8.
So to find the number of distinct N digit numbers we can start with the number of ways to reach each key in the number pad as one. Then calculate the number of ways for each key N - 1 times.
Algorithm:
- Set MOD as 10^9 + 7
- Create an empty array prevNumWays of size 10 with all values 1.
- Iterate from 1 to n - 1
- Create an empty array of size 10 noOfWays
- Set noOfWays[0] as prevNumWays[4] + prevNumWays[6]
- Set noOfWays[1] as prevNumWays[6] + prevNumWays[8]
- Set noOfWays[2] as prevNumWays[7] + prevNumWays[9]
- Set noOfWays[3] as prevNumWays[4] + prevNumWays[8]
- Set noOfWays[4] as prevNumWays[3] + prevNumWays[9] + prevNumWays[0]
- Set noOfWays[5] as 0
- Set noOfWays[6] as prevNumWays[1] + prevNumWays[7] + prevNumWays[0]
- Set noOfWays[7] as prevNumWays[2] + prevNumWays[6]
- Set noOfWays[8] as prevNumWays[1] + prevNumWays[3]
- Set noOfWays[9] as prevNumWays[4] + prevNumWays[2]
- Set prevNumWays as noOfWays
- Return the sum of prevNumWays modulo MOD
Similar problems