Knight Dialer

Med

#0889Time: O(10 * 3^n) or simply O(3^n) - This is exponential. For each of the 10 starting positions, we explore a tree of depth `n-1`. The branching factor is at most 3 (for digits 4 and 6).Space: O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is `n`.2 companies

Patterns

Dynamic Programming

Companies

Snap Bridgewater Associates

Prompt

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagram:

A chess knight can move as indicated in the chess diagram below:

We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell).

Given an integer n, return how many distinct phone numbers of length n we can dial.

You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps.

As the answer may be very large, return the answer modulo 10⁹ + 7.

Example 1:

Input: n = 1
Output: 10
Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2:

Input: n = 2
Output: 20
Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Example 3:

Input: n = 3131
Output: 136006598
Explanation: Please take care of the mod.

Constraints:

1 <= n <= 5000

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly translates the problem into a recursive function. We can think of this as exploring a tree of all possible knight moves. We define a function that takes the number of remaining jumps and the current digit as input. This function recursively calls itself for all valid next moves. The base case is when there are no jumps left. We sum the results from all possible starting digits.

Algorithm

Define the graph of knight moves on the phone pad, for example, using an adjacency list.
Create a recursive function, let's call it count(jumps, digit), that calculates the number of distinct numbers that can be formed with jumps remaining, starting from the current digit.
Base Case: If jumps == 0, it means a valid number of length n has been formed. Return 1.
Recursive Step: Initialize a counter ways = 0. Iterate through each nextDigit that is a valid knight's move from the current digit. For each nextDigit, recursively call count(jumps - 1, nextDigit) and add the result to ways.
The main function will call the recursive helper for each possible starting digit (0 through 9) with n - 1 jumps and sum up the results to get the total count. All additions should be performed modulo 10^9 + 7.

Walkthrough

We first define the possible moves for the knight from each numeric key on the phone pad. This can be stored in an adjacency list, like a Map<Integer, int[]> or a 2D array.

We create a recursive helper function, say countPaths(remainingJumps, currentDigit).

The base case for the recursion is when remainingJumps is 0. This means we have successfully formed a number of the required length, so we return 1.

In the recursive step, we iterate through all possible next digits reachable from currentDigit. For each valid nextDigit, we make a recursive call countPaths(remainingJumps - 1, nextDigit).

We sum up the results of these recursive calls. This sum represents the total number of distinct numbers that can be formed starting from currentDigit with remainingJumps.

The main function initializes a total count to zero. It then iterates through all possible starting digits (0-9) and calls the recursive function with n-1 jumps. The results are summed up to get the final answer.

This method explores every single possible path, leading to many redundant calculations for the same subproblems.

1class Solution {2    private int[][] moves = {3        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},4        {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}5    };6    private int MOD = 1_000_000_007;7 8    public int knightDialer(int n) {9        if (n == 1) return 10;10        long totalCount = 0;11        for (int i = 0; i <= 9; i++) {12            totalCount = (totalCount + countPaths(n - 1, i)) % MOD;13        }14        return (int) totalCount;15    }16 17    private long countPaths(int remainingJumps, int currentDigit) {18        if (remainingJumps == 0) {19            return 1;20        }21 22        long count = 0;23        for (int nextDigit : moves[currentDigit]) {24            count = (count + countPaths(remainingJumps - 1, nextDigit)) % MOD;25        }26        return count;27    }28}

Complexity

Time

O(10 * 3^n) or simply O(3^n) - This is exponential. For each of the 10 starting positions, we explore a tree of depth `n-1`. The branching factor is at most 3 (for digits 4 and 6).

Space

O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is `n`.

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.
Serves as a good foundation for more optimized dynamic programming solutions.

Cons

Extremely inefficient due to the massive number of redundant computations for the same subproblems (e.g., calculating the number of paths of length k from digit d multiple times).
Will result in a 'Time Limit Exceeded' (TLE) error for the constraints given in the problem.

This approach improves upon the brute-force recursion by caching the results of subproblems, a technique known as memoization. The recursive structure remains the same, but before computing the result for a state (remainingJumps, currentDigit), we check if it has already been computed and stored in a memoization table. If so, we return the cached value, avoiding redundant computations and drastically reducing the time complexity.

Algorithm

The algorithm is fundamentally the same as the brute-force recursion, but with an added caching layer.
Create a memoization table, memo[n][10], to store the results of subproblems. Initialize it with a sentinel value (e.g., 0 or -1) to indicate that a state has not been computed.
Modify the recursive function count(jumps, digit):
- Base Case: If jumps == 0, return 1.
- Memoization Check: Before any computation, check if memo[jumps][digit] contains a previously computed result. If so, return it immediately.
- Recursive Step: If the result is not in the cache, compute it by summing the results of count(jumps - 1, nextDigit) for all valid moves.
- Cache Update: Before returning the newly computed value, store it in memo[jumps][digit].
The main function remains the same: call the helper for all 10 starting digits with n-1 jumps and sum the results.

Walkthrough

The core idea is to recognize that the subproblem countPaths(remainingJumps, currentDigit) is solved multiple times with the same arguments. We can store its result to avoid re-calculation.

We use a 2D array, memo[n][10], to store the results. memo[i][j] will store the number of ways to dial a number by making i jumps starting from digit j.

The recursive function countPaths(remainingJumps, currentDigit) is modified:

First, it checks if memo[remainingJumps][currentDigit] has a valid stored value. If yes, it returns that value immediately.
If not, it proceeds with the calculation as in the brute-force approach.
Before returning the newly computed result, it stores it in memo[remainingJumps][currentDigit] for future use.

All calculations are performed modulo 10^9 + 7 to prevent overflow and get the correct answer.

The main function initializes the memoization table, then calls the helper for each starting digit, summing the results.

1class Solution {2    private int[][] moves = {3        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},4        {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}5    };6    private int MOD = 1_000_000_007;7    private int[][] memo;8 9    public int knightDialer(int n) {10        memo = new int[n + 1][10];11        long totalCount = 0;12        for (int i = 0; i <= 9; i++) {13            totalCount = (totalCount + countPaths(n, i)) % MOD;14        }15        return (int) totalCount;16    }17 18    // counts paths of length 'len' ending at 'digit'19    private int countPaths(int len, int digit) {20        if (len == 1) {21            return 1;22        }23        if (memo[len][digit] != 0) {24            return memo[len][digit];25        }26 27        long count = 0;28        for (int prevDigit : moves[digit]) { // This should be reverse moves, let's fix logic29            // The logic should be: count(len, digit) = sum(count(len-1, prev_digit))30            // where prev_digit can jump to digit. Let's adjust the main call.31        }32        // Correct logic is in the main function calling with n-1 jumps33        // Let's use the original logic for clarity.34        return countPathsHelper(len - 1, digit);35    }36 37    // counts paths with 'jumps' remaining, starting from 'digit'38    private int countPathsHelper(int remainingJumps, int currentDigit) {39        if (remainingJumps == 0) {40            return 1;41        }42        if (memo[remainingJumps][currentDigit] != 0) {43            return memo[remainingJumps][currentDigit];44        }45 46        long count = 0;47        for (int nextDigit : moves[currentDigit]) {48            count = (count + countPathsHelper(remainingJumps - 1, nextDigit)) % MOD;49        }50        51        memo[remainingJumps][currentDigit] = (int) count;52        return (int) count;53    }54    // In main: call countPathsHelper(n-1, i) for each i55}

Complexity

Time

O(n) - Each state `(jumps, digit)` is computed only once. There are `n * 10` states. The computation for each state involves a small constant number of operations (looping through next moves).

Space

O(n) - We need a memoization table of size `n x 10`, and the recursion stack can go up to a depth of `n`.

Trade-offs

Pros

Drastically more efficient than brute force, changing the complexity from exponential to linear.
Guaranteed to solve the problem within the time limits for the given constraints.
Maintains a readable, recursive structure that is close to the problem's definition.

Cons

Uses O(n) space for the memoization table, which might be substantial for very large n (though acceptable for the given constraints).
Still has the overhead associated with recursion, which can make it slightly slower than an iterative bottom-up approach.

This approach converts the top-down memoized recursion into a bottom-up iterative solution. We build up the solution for length i using the solutions for length i-1. Let dp[i][j] be the number of ways to form a number of length i ending at digit j. The recurrence is dp[i][j] = sum(dp[i-1][k]) for all k that can jump to j. We can observe that to compute the counts for length i, we only need the counts from length i-1. This allows us to optimize space by only keeping track of the counts for the previous length, reducing space complexity from O(n) to O(1). This is the most practical and efficient solution for the given constraints.

Algorithm

Let dp[j] be the number of ways to form a number of the current length ending in digit j.
Initialize a 1D array dp of size 10 with all elements set to 1. This represents the base case: for a number of length 1, there is one way to end on any digit (by starting there).
Loop n-1 times, as we need to perform n-1 jumps.
Inside the loop, create a temporary array next_dp of size 10, initialized to zeros.
Iterate through each digit from_digit from 0 to 9. The value dp[from_digit] is the number of ways to have arrived at this digit in the previous step.
For each to_digit reachable from from_digit, add dp[from_digit] to next_dp[to_digit] (modulo MOD).
After iterating through all from_digits, the next_dp array contains the counts for the new length. Update dp by assigning next_dp to it.
After the main loop finishes, the dp array holds the counts for numbers of length n. The final answer is the sum of all elements in this dp array.

Walkthrough

We use a 1D array, dp, of size 10. dp[j] will store the number of ways to form a number of the current length ending in digit j.

We initialize dp with all 1s. This represents the base case: for a number of length 1, there is exactly one way to end on any digit (by starting there).

We then loop n-1 times, where each iteration corresponds to adding one more digit to the number (i.e., one more jump).

In each iteration, we create a temporary array, next_dp, to store the counts for the new length. We calculate next_dp[to] by summing up the dp[from] values for all from digits that can jump to to. After computing all values for next_dp, we update dp = next_dp for the next iteration.

After n-1 iterations, the dp array holds the counts for numbers of length n. The final answer is the sum of all elements in the dp array, modulo 10^9 + 7.

1class Solution {2    public int knightDialer(int n) {3        if (n == 1) return 10;4 5        int MOD = 1_000_000_007;6        // moves[i] is the list of numbers you can jump TO from i7        int[][] moves = {8            {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},9            {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}10        };11 12        long[] dp = new long[10];13        java.util.Arrays.fill(dp, 1); // dp for length 114 15        // Iterate for jumps to form lengths 2 through n16        for (int i = 1; i < n; i++) {17            long[] next_dp = new long[10];18            // For each starting digit 'from' for this jump19            for (int from = 0; from <= 9; from++) {20                // For each destination digit 'to'21                for (int to : moves[from]) {22                    next_dp[to] = (next_dp[to] + dp[from]) % MOD;23                }24            }25            dp = next_dp;26        }27 28        long totalCount = 0;29        for (long count : dp) {30            totalCount = (totalCount + count) % MOD;31        }32 33        return (int) totalCount;34    }35}

Complexity

Time

O(n) - The outer loop runs `n-1` times. The inner loops iterate through the 10 digits and their moves. Since the total number of moves in the graph is a small constant, each iteration of the outer loop takes constant time. Thus, the total time is proportional to `n`.

Space

O(1) - We only use two arrays of size 10, which is constant space regardless of `n`.

Trade-offs

Pros

Highly efficient in both time (linear) and space (constant).
Avoids recursion overhead, making it slightly faster in practice than the memoized version.
The most practical and common solution for this type of problem within typical competitive programming constraints.

Cons

Can be slightly less intuitive to formulate than the recursive top-down approach for those new to DP.

This is a highly advanced and powerful technique for solving linear recurrence relations, which is what our DP formulation represents. The state transition from one length to the next can be described by a matrix multiplication. If v_i is a vector representing the counts for each digit at length i, then v_{i+1} = T * v_i, where T is a constant 10x10 transition matrix. To find the counts for length n, we need to compute v_n = T^(n-1) * v_1. The matrix power T^(n-1) can be calculated efficiently in logarithmic time using binary exponentiation (also known as exponentiation by squaring).

Algorithm

Represent the DP state transition as a matrix multiplication. Let V_i be a 10x1 column vector where V_i[j] is the number of ways to form a number of length i ending at digit j. Then V_i = M * V_{i-1}.
Construct the 10x10 transition matrix M, where M[j][k] = 1 if a knight can jump from digit k to j, and 0 otherwise.
The problem reduces to finding V_n = M^(n-1) * V_1. Since V_1 is a vector of all ones, the total count is the sum of all elements in the resulting matrix M^(n-1).
Implement a function for multiplying two 10x10 matrices.
Implement a function to compute M^(n-1) using the binary exponentiation (or exponentiation by squaring) algorithm. This algorithm calculates the power in O(log n) matrix multiplications.
Calculate ResultMatrix = M^(n-1).
Sum all elements of ResultMatrix to get the final answer.

Walkthrough

The DP recurrence dp[i][j] = sum(dp[i-1][k]) over all k that can jump to j is a linear transformation. This transformation can be captured by a 10x10 matrix M.

Let V_i be a column vector of the counts for length i. Then V_i = M * V_{i-1}. By extension, V_n = M^(n-1) * V_1.

The initial vector V_1 (for length 1) is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]^T.

The total number of ways is the sum of elements in V_n. This is equivalent to (sum_vector) * V_n, where sum_vector is [1, 1, ..., 1]. This simplifies to summing all elements of the final matrix M^(n-1).

The algorithm is:

Construct the 10x10 transition matrix M.
Compute ResultMatrix = M^(n-1) using binary exponentiation for matrices.
The total number of ways is the sum of all elements in ResultMatrix.

1class Solution {2    int MOD = 1_000_000_007;3 4    public int knightDialer(int n) {5        if (n == 1) return 10;6 7        long[][] transitionMatrix = {8            {0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, // 0 <- 4, 69            {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, // 1 <- 6, 810            {0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, // 2 <- 7, 911            {0, 0, 0, 0, 1, 0, 0, 0, 1, 0}, // 3 <- 4, 812            {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, // 4 <- 0, 3, 913            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 5 <-14            {1, 1, 0, 0, 0, 0, 0, 1, 0, 0}, // 6 <- 0, 1, 715            {0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, // 7 <- 2, 616            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // 8 <- 1, 317            {0, 0, 1, 0, 1, 0, 0, 0, 0, 0}  // 9 <- 2, 418        };19 20        long[][] resultMatrix = matrixPower(transitionMatrix, n - 1);21 22        long totalCount = 0;23        for (int i = 0; i < 10; i++) {24            for (int j = 0; j < 10; j++) {25                totalCount = (totalCount + resultMatrix[i][j]) % MOD;26            }27        }28        return (int) totalCount;29    }30 31    private long[][] matrixMultiply(long[][] A, long[][] B) {32        long[][] C = new long[10][10];33        for (int i = 0; i < 10; i++) {34            for (int j = 0; j < 10; j++) {35                for (int k = 0; k < 10; k++) {36                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;37                }38            }39        }40        return C;41    }42 43    private long[][] matrixPower(long[][] base, int exp) {44        long[][] result = new long[10][10];45        for (int i = 0; i < 10; i++) result[i][i] = 1; // Identity matrix46        47        while (exp > 0) {48            if (exp % 2 == 1) result = matrixMultiply(result, base);49            base = matrixMultiply(base, base);50            exp /= 2;51        }52        return result;53    }54}

Complexity

Time

O(log n) - More precisely, `O(K^3 * log n)`, where `K=10` is the number of digits. Matrix multiplication is `O(K^3)`, and binary exponentiation performs `O(log n)` such multiplications. Since `K` is constant, the complexity is logarithmic in `n`.

Space

O(1) - We need to store a few 10x10 matrices, which is constant space, `O(K^2)` where K=10.

Trade-offs

Pros

Asymptotically the fastest approach with O(log n) time complexity.
Extremely efficient for very large values of n where an O(n) solution would be too slow.
Space complexity is constant.

Cons

Significantly more complex to implement compared to the iterative DP approach.
The constant factor for time complexity is large (K^3 for a KxK matrix). For the given constraints (n <= 5000), the simpler O(n) DP approach might be faster in practice due to smaller constant factors.

Solutions

Solution

1public class Solution { public int KnightDialer ( int n ) { if ( n == 1 ) return 10 ; int A = 4 ; int B = 2 ; int C = 2 ; int D = 1 ; int MOD = ( int ) 1 e9 + 7 ; for ( int i = 0 ; i < n - 1 ; i ++) { int tempA = A ; int tempB = B ; int tempC = C ; int tempD = D ; A = (( 2 * tempB ) % MOD + ( 2 * tempC ) % MOD ) % MOD ; B = tempA ; C = ( tempA + ( 2 * tempD ) % MOD ) % MOD ; D = tempC ; } int ans = ( A + B ) % MOD ; ans = ( ans + C ) % MOD ; return ( ans + D ) % MOD ; } }

1class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int knightDialer ( int n ) { if ( n == 1 ) { return 10 ; } long [] f = new long [ 10 ]; Arrays . fill ( f , 1 ); while (-- n > 0 ) { long [] t = new long [ 10 ]; t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) { f [ i ] = t [ i ] % MOD ; } } long ans = 0 ; for ( long v : f ) { ans = ( ans + v ) % MOD ; } return ( int ) ans ; } }

1using ll = long long ; class Solution { public: int knightDialer ( int n ) { if ( n == 1 ) return 10 ; int mod = 1e9 + 7 ; vector < ll > f ( 10 , 1ll ); while ( -- n ) { vector < ll > t ( 10 ); t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) f [ i ] = t [ i ] % mod ; } ll ans = accumulate ( f . begin (), f . end (), 0ll ); return ( int ) ( ans % mod ); } };

1class Solution : def knightDialer ( self , n : int ) -> int : if n == 1 : return 10 f = [ 1 ] * 10 for _ in range ( n - 1 ): t = [ 0 ] * 10 t [ 0 ] = f [ 4 ] + f [ 6 ] t [ 1 ] = f [ 6 ] + f [ 8 ] t [ 2 ] = f [ 7 ] + f [ 9 ] t [ 3 ] = f [ 4 ] + f [ 8 ] t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ] t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ] t [ 7 ] = f [ 2 ] + f [ 6 ] t [ 8 ] = f [ 1 ] + f [ 3 ] t [ 9 ] = f [ 2 ] + f [ 4 ] f = t return sum ( t ) % ( 10 ** 9 + 7 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution { public int KnightDialer ( int n ) { if ( n == 1 ) return 10 ; int A = 4 ; int B = 2 ; int C = 2 ; int D = 1 ; int MOD = ( int ) 1 e9 + 7 ; for ( int i = 0 ; i < n - 1 ; i ++) { int tempA = A ; int tempB = B ; int tempC = C ; int tempD = D ; A = (( 2 * tempB ) % MOD + ( 2 * tempC ) % MOD ) % MOD ; B = tempA ; C = ( tempA + ( 2 * tempD ) % MOD ) % MOD ; D = tempC ; } int ans = ( A + B ) % MOD ; ans = ( ans + C ) % MOD ; return ( ans + D ) % MOD ; } }

1class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int knightDialer ( int n ) { if ( n == 1 ) { return 10 ; } long [] f = new long [ 10 ]; Arrays . fill ( f , 1 ); while (-- n > 0 ) { long [] t = new long [ 10 ]; t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) { f [ i ] = t [ i ] % MOD ; } } long ans = 0 ; for ( long v : f ) { ans = ( ans + v ) % MOD ; } return ( int ) ans ; } }

1using ll = long long ; class Solution { public: int knightDialer ( int n ) { if ( n == 1 ) return 10 ; int mod = 1e9 + 7 ; vector < ll > f ( 10 , 1ll ); while ( -- n ) { vector < ll > t ( 10 ); t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) f [ i ] = t [ i ] % mod ; } ll ans = accumulate ( f . begin (), f . end (), 0ll ); return ( int ) ( ans % mod ); } };

1class Solution : def knightDialer ( self , n : int ) -> int : if n == 1 : return 10 f = [ 1 ] * 10 for _ in range ( n - 1 ): t = [ 0 ] * 10 t [ 0 ] = f [ 4 ] + f [ 6 ] t [ 1 ] = f [ 6 ] + f [ 8 ] t [ 2 ] = f [ 7 ] + f [ 9 ] t [ 3 ] = f [ 4 ] + f [ 8 ] t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ] t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ] t [ 7 ] = f [ 2 ] + f [ 6 ] t [ 8 ] = f [ 1 ] + f [ 3 ] t [ 9 ] = f [ 2 ] + f [ 4 ] f = t return sum ( t ) % ( 10 ** 9 + 7 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.