onenoughtone
Code Implementation
Knight Dialer Implementation
Below is the implementation of the knight dialer:
solution.js
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212/** * Calculate the number of distinct phone numbers of length n that can be dialed. * Dynamic Programming approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialer(n) { const MOD = 1000000007; // Define the possible knight moves for each digit const moves = [ [4, 6], // From digit 0 [6, 8], // From digit 1 [7, 9], // From digit 2 [4, 8], // From digit 3 [0, 3, 9], // From digit 4 [], // From digit 5 [0, 1, 7], // From digit 6 [2, 6], // From digit 7 [1, 3], // From digit 8 [2, 4] // From digit 9 ]; // Initialize DP array // dp[i][j] = number of distinct phone numbers of length i+1 that end with digit j const dp = Array(n).fill().map(() => Array(10).fill(0)); // Base cases: there is one way to dial a number of length 1 for each digit for (let j = 0; j < 10; j++) { dp[0][j] = 1; } // Fill DP array for (let i = 1; i < n; i++) { for (let j = 0; j < 10; j++) { // For each digit j, consider all possible previous digits that can jump to j for (const prev of moves[j]) { dp[i][j] = (dp[i][j] + dp[i - 1][prev]) % MOD; } } } // Calculate the final answer: sum of dp[n-1][j] for all j from 0 to 9 let result = 0; for (let j = 0; j < 10; j++) { result = (result + dp[n - 1][j]) % MOD; } return result;} /** * Calculate the number of distinct phone numbers of length n that can be dialed. * Space-Optimized Dynamic Programming approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialerOptimized(n) { const MOD = 1000000007; // Define the possible knight moves for each digit const moves = [ [4, 6], // From digit 0 [6, 8], // From digit 1 [7, 9], // From digit 2 [4, 8], // From digit 3 [0, 3, 9], // From digit 4 [], // From digit 5 [0, 1, 7], // From digit 6 [2, 6], // From digit 7 [1, 3], // From digit 8 [2, 4] // From digit 9 ]; // Initialize arrays for previous and current jumps let prev = Array(10).fill(1); // Base case: one way to dial a number of length 1 for each digit let curr = Array(10).fill(0); // Fill arrays for (let i = 1; i < n; i++) { // Reset curr array curr = Array(10).fill(0); for (let j = 0; j < 10; j++) { // For each digit j, consider all possible previous digits that can jump to j for (const prevDigit of moves[j]) { curr[j] = (curr[j] + prev[prevDigit]) % MOD; } } // Update prev array prev = [...curr]; } // Calculate the final answer: sum of prev[j] for all j from 0 to 9 return prev.reduce((sum, val) => (sum + val) % MOD, 0);} /** * Calculate the number of distinct phone numbers of length n that can be dialed. * Matrix Exponentiation approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialerMatrix(n) { const MOD = 1000000007; // If n is 1, return 10 (one way to dial a number of length 1 for each digit) if (n === 1) { return 10; } // Define the adjacency matrix const matrix = [ [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], // From digit 0 [0, 0, 0, 0, 0, 0, 1, 0, 1, 0], // From digit 1 [0, 0, 0, 0, 0, 0, 0, 1, 0, 1], // From digit 2 [0, 0, 0, 0, 1, 0, 0, 0, 1, 0], // From digit 3 [1, 0, 0, 1, 0, 0, 0, 0, 0, 1], // From digit 4 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // From digit 5 [1, 1, 0, 0, 0, 0, 0, 1, 0, 0], // From digit 6 [0, 0, 1, 0, 0, 0, 1, 0, 0, 0], // From digit 7 [0, 1, 0, 1, 0, 0, 0, 0, 0, 0], // From digit 8 [0, 0, 1, 0, 1, 0, 0, 0, 0, 0] // From digit 9 ]; // Compute matrix^(n-1) const resultMatrix = matrixPower(matrix, n - 1, MOD); // Calculate the final answer: sum of all elements in the result matrix let result = 0; for (let i = 0; i < 10; i++) { for (let j = 0; j < 10; j++) { result = (result + resultMatrix[i][j]) % MOD; } } return result;} /** * Compute the power of a matrix using binary exponentiation. * * @param {number[][]} matrix - The base matrix * @param {number} n - The exponent * @param {number} mod - The modulo value * @return {number[][]} - The resulting matrix */function matrixPower(matrix, n, mod) { // Base case: matrix^0 = identity matrix if (n === 0) { const identity = Array(10).fill().map(() => Array(10).fill(0)); for (let i = 0; i < 10; i++) { identity[i][i] = 1; } return identity; } // If n is odd, compute matrix^(n-1) * matrix if (n % 2 === 1) { const result = matrixPower(matrix, n - 1, mod); return multiplyMatrices(result, matrix, mod); } // If n is even, compute (matrix^(n/2))^2 const half = matrixPower(matrix, Math.floor(n / 2), mod); return multiplyMatrices(half, half, mod);} /** * Multiply two matrices. * * @param {number[][]} a - First matrix * @param {number[][]} b - Second matrix * @param {number} mod - The modulo value * @return {number[][]} - The product of the two matrices */function multiplyMatrices(a, b, mod) { const result = Array(10).fill().map(() => Array(10).fill(0)); for (let i = 0; i < 10; i++) { for (let j = 0; j < 10; j++) { for (let k = 0; k < 10; k++) { result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod; } } } return result;} // Test casesconsole.log(knightDialer(1)); // 10console.log(knightDialer(2)); // 20console.log(knightDialer(3)); // 46console.log(knightDialer(4)); // 104console.log(knightDialer(3131)); // 136006598 console.log(knightDialerOptimized(1)); // 10console.log(knightDialerOptimized(2)); // 20console.log(knightDialerOptimized(3)); // 46console.log(knightDialerOptimized(4)); // 104console.log(knightDialerOptimized(3131)); // 136006598 console.log(knightDialerMatrix(1)); // 10console.log(knightDialerMatrix(2)); // 20console.log(knightDialerMatrix(3)); // 46console.log(knightDialerMatrix(4)); // 104console.log(knightDialerMatrix(3131)); // 136006598Step-by-Step Explanation
Let's break down the implementation:
- Define Knight Moves: Define the possible knight moves for each digit on the phone keypad, considering the L-shaped movement pattern of a chess knight.
- Initialize DP Array: Set up a dynamic programming array to keep track of the number of distinct phone numbers of a certain length ending with each digit.
- Establish Base Cases: For a phone number of length 1, there is exactly one way to dial each digit (by simply pressing that digit).
- Fill DP Array: For each length and each digit, calculate the number of ways to reach that digit by considering all possible previous digits that can lead to it through a valid knight move.
- Calculate Final Answer: Sum up the number of ways to dial a phone number of the target length ending with each digit, applying the modulo operation to avoid integer overflow.
String Problems
Learning Objective
Implement the knight dialer solution in different programming languages.
Knight Dialer Implementation
Below is the implementation of the knight dialer in different programming languages. Select a language tab to view the corresponding code.
solution.js
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212/** * Calculate the number of distinct phone numbers of length n that can be dialed. * Dynamic Programming approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialer(n) { const MOD = 1000000007; // Define the possible knight moves for each digit const moves = [ [4, 6], // From digit 0 [6, 8], // From digit 1 [7, 9], // From digit 2 [4, 8], // From digit 3 [0, 3, 9], // From digit 4 [], // From digit 5 [0, 1, 7], // From digit 6 [2, 6], // From digit 7 [1, 3], // From digit 8 [2, 4] // From digit 9 ]; // Initialize DP array // dp[i][j] = number of distinct phone numbers of length i+1 that end with digit j const dp = Array(n).fill().map(() => Array(10).fill(0)); // Base cases: there is one way to dial a number of length 1 for each digit for (let j = 0; j < 10; j++) { dp[0][j] = 1; } // Fill DP array for (let i = 1; i < n; i++) { for (let j = 0; j < 10; j++) { // For each digit j, consider all possible previous digits that can jump to j for (const prev of moves[j]) { dp[i][j] = (dp[i][j] + dp[i - 1][prev]) % MOD; } } } // Calculate the final answer: sum of dp[n-1][j] for all j from 0 to 9 let result = 0; for (let j = 0; j < 10; j++) { result = (result + dp[n - 1][j]) % MOD; } return result;} /** * Calculate the number of distinct phone numbers of length n that can be dialed. * Space-Optimized Dynamic Programming approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialerOptimized(n) { const MOD = 1000000007; // Define the possible knight moves for each digit const moves = [ [4, 6], // From digit 0 [6, 8], // From digit 1 [7, 9], // From digit 2 [4, 8], // From digit 3 [0, 3, 9], // From digit 4 [], // From digit 5 [0, 1, 7], // From digit 6 [2, 6], // From digit 7 [1, 3], // From digit 8 [2, 4] // From digit 9 ]; // Initialize arrays for previous and current jumps let prev = Array(10).fill(1); // Base case: one way to dial a number of length 1 for each digit let curr = Array(10).fill(0); // Fill arrays for (let i = 1; i < n; i++) { // Reset curr array curr = Array(10).fill(0); for (let j = 0; j < 10; j++) { // For each digit j, consider all possible previous digits that can jump to j for (const prevDigit of moves[j]) { curr[j] = (curr[j] + prev[prevDigit]) % MOD; } } // Update prev array prev = [...curr]; } // Calculate the final answer: sum of prev[j] for all j from 0 to 9 return prev.reduce((sum, val) => (sum + val) % MOD, 0);} /** * Calculate the number of distinct phone numbers of length n that can be dialed. * Matrix Exponentiation approach. * * @param {number} n - Length of the phone number * @return {number} - Number of distinct phone numbers */function knightDialerMatrix(n) { const MOD = 1000000007; // If n is 1, return 10 (one way to dial a number of length 1 for each digit) if (n === 1) { return 10; } // Define the adjacency matrix const matrix = [ [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], // From digit 0 [0, 0, 0, 0, 0, 0, 1, 0, 1, 0], // From digit 1 [0, 0, 0, 0, 0, 0, 0, 1, 0, 1], // From digit 2 [0, 0, 0, 0, 1, 0, 0, 0, 1, 0], // From digit 3 [1, 0, 0, 1, 0, 0, 0, 0, 0, 1], // From digit 4 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // From digit 5 [1, 1, 0, 0, 0, 0, 0, 1, 0, 0], // From digit 6 [0, 0, 1, 0, 0, 0, 1, 0, 0, 0], // From digit 7 [0, 1, 0, 1, 0, 0, 0, 0, 0, 0], // From digit 8 [0, 0, 1, 0, 1, 0, 0, 0, 0, 0] // From digit 9 ]; // Compute matrix^(n-1) const resultMatrix = matrixPower(matrix, n - 1, MOD); // Calculate the final answer: sum of all elements in the result matrix let result = 0; for (let i = 0; i < 10; i++) { for (let j = 0; j < 10; j++) { result = (result + resultMatrix[i][j]) % MOD; } } return result;} /** * Compute the power of a matrix using binary exponentiation. * * @param {number[][]} matrix - The base matrix * @param {number} n - The exponent * @param {number} mod - The modulo value * @return {number[][]} - The resulting matrix */function matrixPower(matrix, n, mod) { // Base case: matrix^0 = identity matrix if (n === 0) { const identity = Array(10).fill().map(() => Array(10).fill(0)); for (let i = 0; i < 10; i++) { identity[i][i] = 1; } return identity; } // If n is odd, compute matrix^(n-1) * matrix if (n % 2 === 1) { const result = matrixPower(matrix, n - 1, mod); return multiplyMatrices(result, matrix, mod); } // If n is even, compute (matrix^(n/2))^2 const half = matrixPower(matrix, Math.floor(n / 2), mod); return multiplyMatrices(half, half, mod);} /** * Multiply two matrices. * * @param {number[][]} a - First matrix * @param {number[][]} b - Second matrix * @param {number} mod - The modulo value * @return {number[][]} - The product of the two matrices */function multiplyMatrices(a, b, mod) { const result = Array(10).fill().map(() => Array(10).fill(0)); for (let i = 0; i < 10; i++) { for (let j = 0; j < 10; j++) { for (let k = 0; k < 10; k++) { result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod; } } } return result;} // Test casesconsole.log(knightDialer(1)); // 10console.log(knightDialer(2)); // 20console.log(knightDialer(3)); // 46console.log(knightDialer(4)); // 104console.log(knightDialer(3131)); // 136006598 console.log(knightDialerOptimized(1)); // 10console.log(knightDialerOptimized(2)); // 20console.log(knightDialerOptimized(3)); // 46console.log(knightDialerOptimized(4)); // 104console.log(knightDialerOptimized(3131)); // 136006598 console.log(knightDialerMatrix(1)); // 10console.log(knightDialerMatrix(2)); // 20console.log(knightDialerMatrix(3)); // 46console.log(knightDialerMatrix(4)); // 104console.log(knightDialerMatrix(3131)); // 136006598Step-by-Step Explanation
1Define Knight Moves
Define the possible knight moves for each digit on the phone keypad, considering the L-shaped movement pattern of a chess knight.
2Initialize DP Array
Set up a dynamic programming array to keep track of the number of distinct phone numbers of a certain length ending with each digit.
3Establish Base Cases
For a phone number of length 1, there is exactly one way to dial each digit (by simply pressing that digit).
4Fill DP Array
For each length and each digit, calculate the number of ways to reach that digit by considering all possible previous digits that can lead to it through a valid knight move.
5Calculate Final Answer
Sum up the number of ways to dial a phone number of the target length ending with each digit, applying the modulo operation to avoid integer overflow.
Language-Specific Notes
javascript
- JavaScript's Array.fill().map() is used to create multi-dimensional arrays.
- The % operator is used for the modulo operation to avoid integer overflow.
- The spread operator (...) is used to create a copy of an array in the optimized approach.
- The reduce() method is used to sum up all elements in an array.
- Math.floor() is used to round down to the nearest integer in the matrix exponentiation approach.
python
- Python's list comprehension [[0] * 10 for _ in range(n)] is used to create multi-dimensional arrays.
- The % operator is used for the modulo operation to avoid integer overflow.
- The copy() method is used to create a copy of an array in the optimized approach.
- The sum() function is used to sum up all elements in an array.
- The // operator is used for integer division in the matrix exponentiation approach.
java
- Java's multi-dimensional arrays are created using the new keyword.
- The final keyword is used to define constants (final int MOD = 1000000007).
- The clone() method is used to create a copy of an array in the optimized approach.
- Type casting (int) is used to convert long to int in the matrix multiplication to avoid integer overflow.
- Enhanced for loops (for (int prev : moves[j])) are used for cleaner iteration over arrays.
cpp
- C++'s std::vector is used to create multi-dimensional arrays.
- The const keyword is used to define constants (const int MOD = 1000000007).
- The std::fill() function is used to reset the current array in the optimized approach.
- The const reference parameters (const std::vector
- Type casting (long long) is used in matrix multiplication to avoid integer overflow.
Key Takeaways
- This problem can be solved using dynamic programming by keeping track of the number of ways to reach each digit after a certain number of jumps.
- The space complexity can be optimized by only keeping track of the previous and current states.
- Matrix exponentiation provides an even more efficient solution for large inputs, with a time complexity of O(log n).
- The modulo operation needs to be applied at each step to avoid integer overflow.
- Understanding the constraints of the knight's movement on a phone keypad is crucial for solving this problem.
Try It Yourself
Modify the code to implement an alternative approach and test it with the same examples.
Challenge:
Implement a function that solves the knight dialer problem using a different approach than shown above.
Common Edge Cases
Single Digit
Handle the case where n is 1 (return 10, as there is one way to dial each digit).
n = 1
Digit 5
Handle the special case of digit 5, which has no valid knight moves to any other digit.
The knight cannot move from digit 5 to any other digit.
Large Input
Handle large values of n efficiently to avoid stack overflow or timeout issues.
n = 3131