Company: Publicis Sapient
Difficulty: medium
Knight Dialer Problem Description A chess knight moves in a unique way: it can jump two squares vertically and one square horizontally, or two squares horizontally and one square vertically, forming an L-shape. In this problem, we have a knight on a phone keypad, and it can only stand on numeric cells. Given an integer `n`, the task is to return the number of distinct phone numbers of length `n` that the knight can dial. You can place the knight on any numeric cell initially, and then the knight must make `n - 1` valid jumps to form a number of length `n`. Each jump must follow the knight's movement rules. Since the result could be very large, return the answer modulo 10^9 + 7. #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; // Function to return the number of distinct phone numbers the knight can dial int knightDialer(int n) { // Enter your code here } // Driver code int main() { int n; // n: length of the phone number // Input the length of the phone n