Count of all possible ways to reach a target by a Knight

0 0 8 minutes read

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 10⁹+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)C_Y.

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 % Mod
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) {
        p = (X * p) % Mod;
    }
 
    return p;
}
 
// Function to return the
// inverse of factorial of N
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 % Mod
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!)
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 Code
int main()
{
 
    int N = 3, M = 3;
 
    cout << TotalWaYs(N, M);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
static int Mod = (int) (1e9 + 7);
 
// Function to return X^Y % Mod
static 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 N
static 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 % Mod
static 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 Code
public 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 approach
Mod = int(1e9 + 7)
 
# Function to return X^Y % Mod
def 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 code
N, M = 3, 3
 
print(TotalWays(N, M))
 
# This code is contributed by Stuti Pathak

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
static int Mod = (int)(1e9 + 7);
 
// Function to return X^Y % Mod
static 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 N
static 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 % Mod
static 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 Code
public 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 approach
 
var Mod = 1000000007;
 
// Function to return X^Y % Mod
function 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 N
function 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 % Mod
function 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 Code
var N = 3, M = 3;
document.write( TotalWaYs(N, M));
 
</script>

Output:

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 zambiatek!