Given two integers N, M denoting N×M chessboard, the task is to count the number of ways a knight can reach (N, M) starting from (0, 0). Since the answer can be very large, print the answer modulo 109+7.
Example:
Input: N =3, M= 3
Output: 2
Explanation:
Two ways to reach (3, 3) form (0, 0) are as follows:
(0, 0) ? (1, 2) ? (3, 3)
(0, 0) ? (2, 1) ? (3, 3)
Input: N=4, M=3
Output: 0
Explanation: No possible way exists to reach (4, 3) form (0, 0).
Approach: Idea here is to observe the pattern that each move increments the value of the x-coordinate + value of y-coordinate by 3. Follow the steps below to solve the problem.
- If (N + M) is not divisible by 3 then no possible path exists.
- If (N + M) % 3==0 then count the number of moves of type (+1, +2) i.e, X and count the number of moves of type (+2, +1) i.e, Y.
- Find the equation of the type (+1, +2) i.e. X + 2Y = N
- Find the equation of the type (+2, +1) i.e. 2X + Y = M
- Find the calculated values of X and Y, if X < 0 or Y < 0, then no possible path exists.
- Otherwise, calculate (X+Y)CY.
Below is the implementation of the above approach:
C++14
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;const int Mod = 1e9 + 7;// Function to return X^Y % Modint power(int X, int Y, int Mod){ // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if (Y & 1) { p = (X * p) % Mod; } return p;}// Function to return the// inverse of factorial of Nint Inversefactorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod);}// Function to return factorial// of n % Modint factorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact;}// Function to return the value// of n! / (( n- k)! * k!)int nck(int N, int K){ int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod;}// Function to return the count of// ways to reach (n, m) from (0, 0)int TotalWaYs(int N, int M){ // If (N + M) % 3 != 0 if ((N + M) % 3 != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y);}// Driver Codeint main(){ int N = 3, M = 3; cout << TotalWaYs(N, M); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{static int Mod = (int) (1e9 + 7);// Function to return X^Y % Modstatic int power(int X, int Y, int Mod){ // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if ((Y & 1) != 0) { p = (X * p) % Mod; } return p;}// Function to return the// inverse of factorial of Nstatic int Inversefactorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod);}// Function to return factorial// of n % Modstatic int factorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact;}// Function to return the value// of n! / (( n- k)! * k!)static int nck(int N, int K){ int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod;}// Function to return the count of// ways to reach (n, m) from (0, 0)static int TotalWaYs(int N, int M){ // If (N + M) % 3 != 0 if (((N + M) % 3 )!= 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y);}// Driver Codepublic static void main(String[] args){ int N = 3, M = 3; System.out.print(TotalWaYs(N, M));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to implement# above approachMod = int(1e9 + 7)# Function to return X^Y % Moddef power(X, Y, Mod): # Base case if Y == 0: return 1 p = power(X, Y // 2, Mod) % Mod p = (p * p) % Mod if Y & 1: p = (X * p) % Mod return p# Function to return the # inverse of factorial of N def Inversefactorial(N): # Base case if N <= 0: return 1 fact = 1 for i in range(1, N + 1): fact = (fact * i) % Mod return power(fact, Mod - 2, Mod)# Function to return factorial # of n % Mod def factorial(N): # Base case if N <= 0: return 1 fact = 1 for i in range(1, N + 1): fact = (fact * i) % Mod return fact# Function to return the value # of n! / (( n- k)! * k!) def nck(N, K): factN = factorial(N) inv = Inversefactorial(K) invFact = Inversefactorial(N - K) return (((factN * inv) % Mod) * invFact) % Mod# Function to return the count of # ways to reach (n, m) from (0, 0) def TotalWays(N, M): # If (N + M) % 3 != 0 if (N + M) % 3 != 0: # No possible way exists return 0 # Calculate X and Y from the # equations X + 2Y = N # and 2X + Y == M X = N - (N + M) // 3 Y = M - (N + M) // 3 if X < 0 or Y < 0: return 0 return nck(X + Y, Y)# Driver codeN, M = 3, 3print(TotalWays(N, M))# This code is contributed by Stuti Pathak |
C#
// C# program to implement// the above approachusing System;class GFG{static int Mod = (int)(1e9 + 7);// Function to return X^Y % Modstatic int power(int X, int Y, int Mod){ // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if ((Y & 1) != 0) { p = (X * p) % Mod; } return p;}// Function to return the// inverse of factorial of Nstatic int Inversefactorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for(int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod);}// Function to return factorial// of n % Modstatic int factorial(int N){ // Base case if (N <= 0) return 1; int fact = 1; for(int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact;}// Function to return the value// of n! / (( n- k)! * k!)static int nck(int N, int K){ int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod;}// Function to return the count of// ways to reach (n, m) from (0, 0)static int TotalWaYs(int N, int M){ // If (N + M) % 3 != 0 if (((N + M) % 3 ) != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y);}// Driver Codepublic static void Main(String[] args){ int N = 3, M = 3; Console.Write(TotalWaYs(N, M));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript Program to implement// the above approachvar Mod = 1000000007;// Function to return X^Y % Modfunction power(X, Y, Mod){ // Base Case if (Y == 0) return 1; var p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if (Y & 1) { p = (X * p) % Mod; } return p;}// Function to return the// inverse of factorial of Nfunction Inversefactorial(N){ // Base case if (N <= 0) return 1; var fact = 1; for (var i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod);}// Function to return factorial// of n % Modfunction factorial(N){ // Base case if (N <= 0) return 1; var fact = 1; for (var i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact;}// Function to return the value// of n! / (( n- k)! * k!)function nck( N, K){ var factN = factorial(N); var inv = Inversefactorial(K); var invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod;}// Function to return the count of// ways to reach (n, m) from (0, 0)function TotalWaYs(N, M){ // If (N + M) % 3 != 0 if ((N + M) % 3 != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M var X = N - (N + M) / 3; var Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y);}// Driver Codevar N = 3, M = 3;document.write( TotalWaYs(N, M));</script> |
Output:
2
Time Complexity: O(X + Y + log(mod)).
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!
