Given an integer N and a chess knight placed in mobile keypad. The task is to count the total distinct N digit numbers which can be formed by the chess knight with N moves. As the answer can be very large give the value of answer modulo 109 + 7.
Note: In each move a chess knight can move 2 units horizontally and one unit vertically or two units vertically and one unit horizontally.
A demo mobile keypad is shown in image where ‘*’ and ‘#’ are not considered as part of a number.
Examples:
Input: N = 1
Output: 10
Explanation: Placing the knight over any numeric cell of the 10 cells is sufficient.Input: N = 2
Output: 20
Explanation: All the valid number are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
Â
Approach: The idea is to find the possible cells that can be reached from a given cell for every cell and add all of them to find the answer. Follow the steps below to solve the problem:
- Initialize the vector v[10, 1], and temp[10].
- Iterate over the range [1, N) using the variable i and perform the following tasks:
- Find the values for all cells in temp[] and then store them in vector v[].
- Initialize the variable sum as 0 to store the answer.
- Iterate over the range [0, 10) using the variable i and perform the following tasks:
- Add the value of v[i] to the variable sum.
- After performing the above steps, print the value of sum as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find the total number of waysint knightCalling(int N){Â Â Â Â int mod = 1000000007;Â
    // Base Case    if (N == 1)        return 10;    vector<int> v(10, 1);    vector<int> temp(10);Â
    // No cell can be reached from a    // cell with value 5    v[5] = 0;    for (int i = 1; i < N; i++)    {               // Find the possible values from all cells        temp[0] = (v[4] + v[6]) % mod;        temp[1] = (v[6] + v[8]) % mod;        temp[2] = (v[7] + v[9]) % mod;        temp[3] = (v[4] + v[8]) % mod;        temp[4] = (v[0] + v[3] + v[9]) % mod;        temp[6] = (v[0] + v[1] + v[7]) % mod;        temp[7] = (v[2] + v[6]) % mod;        temp[8] = (v[1] + v[3]) % mod;        temp[9] = (v[2] + v[4]) % mod;Â
        // Store them        for (int j = 0; j < 10; j++)            v[j] = temp[i];    }Â
    // Find the answer    int sum = 0;    for (int i = 0; i < 10; i++)        sum = (sum + v[i]) % mod;    return sum;}Â
// Driver Codeint main(){Â Â Â Â int N = 2;Â Â Â Â cout << knightCalling(N);}Â
// This code is contributed by Samim Hossain Mondal. |
Java
// Java program for the above approachimport java.util.*;class GFG{Â
// Function to find the total number of waysstatic int knightCalling(int N){Â Â Â Â int mod = 1000000007;Â
    // Base Case    if (N == 1)        return 10;    int []v = new int[10];    int []temp = new int[10];    Arrays.fill(v, 1);Â
    // No cell can be reached from a    // cell with value 5    v[5] = 0;    for (int i = 1; i < N; i++)    {               // Find the possible values from all cells        temp[0] = (v[4] + v[6]) % mod;        temp[1] = (v[6] + v[8]) % mod;        temp[2] = (v[7] + v[9]) % mod;        temp[3] = (v[4] + v[8]) % mod;        temp[4] = (v[0] + v[3] + v[9]) % mod;        temp[6] = (v[0] + v[1] + v[7]) % mod;        temp[7] = (v[2] + v[6]) % mod;        temp[8] = (v[1] + v[3]) % mod;        temp[9] = (v[2] + v[4]) % mod;Â
        // Store them        for (int j = 0; j < 10; j++)            v[i] = temp[i];    }Â
    // Find the answer    int sum = 0;    for (int i = 0; i < 10; i++)        sum = (sum + v[i]) % mod;    return sum;}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int N = 2;Â Â Â Â System.out.print(knightCalling(N));}}Â
// This code is contributed by 29AjayKumar |
Python3
# Python 3Â program for the above approachÂ
# Function to find the total number of waysdef knightCalling(N):Â
    mod = 1000000007Â
    # Base Case    if (N == 1):        return 10    v = [1]*10    temp = [0]*10Â
    # No cell can be reached from a    # cell with value 5    v[5] = 0    for i in range(1, N):               # Find the possible values from all cells        temp[0] = (v[4] + v[6]) % mod        temp[1] = (v[6] + v[8]) % mod        temp[2] = (v[7] + v[9]) % mod        temp[3] = (v[4] + v[8]) % mod        temp[4] = (v[0] + v[3] + v[9]) % mod        temp[6] = (v[0] + v[1] + v[7]) % mod        temp[7] = (v[2] + v[6]) % mod        temp[8] = (v[1] + v[3]) % mod        temp[9] = (v[2] + v[4]) % modÂ
        # Store them        for j in range(10):            v[j] = temp[j]Â
    # Find the answer    sum = 0    for i in range(10):        sum = (sum + v[i]) % mod    return sumÂ
# Driver Codeif __name__ == "__main__":Â
    N = 2    print(knightCalling(N))Â
    # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{Â
  // Function to find the total number of ways  static int knightCalling(int N)  {    int mod = 1000000007;Â
    // Base Case    if (N == 1)      return 10;    int []v = new int[10];    int []temp = new int[10];    for(int i = 0; i < 10; i++) {      v[i] = 1;    }Â
    // No cell can be reached from a    // cell with value 5    v[5] = 0;    for (int i = 1; i < N; i++)    {Â
      // Find the possible values from all cells      temp[0] = (v[4] + v[6]) % mod;      temp[1] = (v[6] + v[8]) % mod;      temp[2] = (v[7] + v[9]) % mod;      temp[3] = (v[4] + v[8]) % mod;      temp[4] = (v[0] + v[3] + v[9]) % mod;      temp[6] = (v[0] + v[1] + v[7]) % mod;      temp[7] = (v[2] + v[6]) % mod;      temp[8] = (v[1] + v[3]) % mod;      temp[9] = (v[2] + v[4]) % mod;Â
      // Store them      for (int j = 0; j < 10; j++)        v[j] = temp[i];    }Â
    // Find the answer    int sum = 0;    for (int i = 0; i < 10; i++)      sum = (sum + v[i]) % mod;    return sum;  }Â
  // Driver Code  public static void Main()  {    int N = 2;    Console.Write(knightCalling(N));  }}Â
// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>Â Â Â Â Â Â Â // JavaScript code for the above approachÂ
       // Function to find the total number of ways       function knightCalling(N) {           let mod = 1000000007;Â
           // Base Case           if (N == 1)               return 10;           let v = new Array(10).fill(1)           let temp = new Array(10).fill(0);Â
           // No cell can be reached from a           // cell with value 5           v[5] = 0;           for (let i = 1; i < N; i++)            {                           // Find the possible values from all cells               temp[0] = (v[4] + v[6]) % mod;               temp[1] = (v[6] + v[8]) % mod;               temp[2] = (v[7] + v[9]) % mod;               temp[3] = (v[4] + v[8]) % mod;               temp[4] = (v[0] + v[3] + v[9]) % mod;               temp[6] = (v[0] + v[1] + v[7]) % mod;               temp[7] = (v[2] + v[6]) % mod;               temp[8] = (v[1] + v[3]) % mod;               temp[9] = (v[2] + v[4]) % mod;Â
               // Store them               for (let i = 0; i < 10; i++)                   v[i] = temp[i];           }Â
           // Find the answer           let sum = 0;           for (let i = 0; i < 10; i++)               sum = (sum + v[i]) % mod;           return sum;       }Â
       // Driver Code       let N = 2;       document.write(knightCalling(N));Â
 // This code is contributed by Potta Lokesh   </script> |
Â
Â
Output
20
Â
Time Complexity: O(N)
Auxiliary Space: O(1)
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
