Knight Dialer

Distinct Phone Numbers of Length n

Problem Description

Given a chess knight and a phone pad, determine how many distinct phone numbers of length n can be dialed. The knight can only stand on a numeric cell (0-9), and its moves must be valid knight jumps. You are allowed to place the knight on any numeric cell initially, and then perform n - 1 jumps. Return the answer modulo 10^9 + 7.

Naive Approach (Brute Force)

A brute-force approach would involve recursively exploring all possible paths of length n from each starting cell. This approach would be highly inefficient due to the overlapping subproblems and exponential time complexity.

Optimal Solution: Dynamic Programming

A more efficient solution is to use dynamic programming. We can define a 2D array dp[i][j] where dp[i][j] represents the number of distinct phone numbers of length i that end at cell j.

Base Case:

• When n = 1, the knight can be on any of the 10 digits. So, dp[1][j] = 1 for all j from 0 to 9.

Recursive Relation:

• To calculate dp[i][j], we need to consider all the cells k from which the knight can jump to cell j. Then, dp[i][j] = sum(dp[i-1][k]) where k are the neighbors of j.

Final Result:

• The final result will be the sum of dp[n][j] for all j from 0 to 9.

Implementation Details:

1. Initialize a 2D array dp of size (n+1) x 10 with all values set to 0.
2. Set the base case: dp[1][j] = 1 for all j from 0 to 9.
3. Define a graph or adjacency list representing the possible knight moves from each cell.
4. Iterate from i = 2 to n:
   • For each cell j from 0 to 9:
     • Iterate through all neighbors k of cell j:
       • dp[i][j] = (dp[i][j] + dp[i-1][k]) % (10^9 + 7)
5. Calculate the sum of dp[n][j] for all j from 0 to 9 and return the result modulo 10^9 + 7.

Example

Let's consider the case when n = 2:

1. Base Case: dp[1][j] = 1 for all j from 0 to 9.
2. Possible moves:
   • 0 can move to 4 and 6
   • 1 can move to 6 and 8
   • 2 can move to 7 and 9
   • 3 can move to 4 and 8
   • 4 can move to 0, 3 and 9
   • 6 can move to 0, 1 and 7
   • 7 can move to 2 and 6
   • 8 can move to 1 and 3
   • 9 can move to 2 and 4
3. Calculating dp[2][j]:
   • dp[2][0] = dp[1][4] + dp[1][6] = 1 + 1 = 2
   • dp[2][1] = dp[1][6] + dp[1][8] = 1 + 1 = 2
   • dp[2][2] = dp[1][7] + dp[1][9] = 1 + 1 = 2
   • dp[2][3] = dp[1][4] + dp[1][8] = 1 + 1 = 2
   • dp[2][4] = dp[1][0] + dp[1][3] + dp[1][9] = 1 + 1 + 1 = 3
   • dp[2][6] = dp[1][0] + dp[1][1] + dp[1][7] = 1 + 1 + 1 = 3
   • dp[2][7] = dp[1][2] + dp[1][6] = 1 + 1 = 2
   • dp[2][8] = dp[1][1] + dp[1][3] = 1 + 1 = 2
   • dp[2][9] = dp[1][2] + dp[1][4] = 1 + 1 = 2
4. Final Result:
   • Sum of dp[2][j] = 2 + 2 + 2 + 2 + 3 + 3 + 2 + 2 + 2 + 2 = 20

Code Implementation (Python)

def knightDialer(n: int) -> int:
    MOD = 10**9 + 7
    moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    }

    dp = [[0] * 10 for _ in range(n + 1)]

    for j in range(10):
        dp[1][j] = 1

    for i in range(2, n + 1):
        for j in range(10):
            for k in moves[j]:
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD

    total_count = 0
    for j in range(10):
        total_count = (total_count + dp[n][j]) % MOD

    return total_count

Complexity Analysis

• Time Complexity: O(n), where n is the given integer representing the length of the phone number. Because, we have nested loops the outer loop goes from i=2 to n and inner loops loops a maximum of 10 times. So, the time complexity is O(n).
• Space Complexity: O(n), due to the dp array of size (n+1) x 10.

Edge Cases

• n = 1: The result should be 10, as the knight can start on any digit.
• n = 2: The result should be 20, as explained in the example.
• Large n: The modulo operation ensures that the result remains within the specified range.