Count paths with distance equal to Manhattan distance

0 0 5 minutes read

Given two points (x1, y1) and (x2, y2) in 2-D coordinate system. The task is to count all the paths whose distance is equal to the Manhattan distance between both the given points.
Examples:

Input: x1 = 2, y1 = 3, x2 = 4, y2 = 5
Output: 6
Input: x1 = 2, y1 = 6, x2 = 4, y2 = 9
Output: 10

Approach: The Manhattan distance between the points (x1, y1) and (x2, y2) will be abs(x1 – x2) + abs(y1 – y2)
Let abs(x1 – x2) = m and abs(y1 – y2) = n
Every path with distance equal to the Manhattan distance will always have m + n edges, m horizontal and n vertical edges. Hence this is a basic case of Combinatorics which is based upon group formation. The idea behind this is the number of ways in which (m + n) different things can be divided into two groups, one containing m items and the other containing n items which is given by ^{m + n}C_n i.e. (m + n)! / m! * n!.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the value of nCk
ll binomialCoeff(int n, int k)
{
    ll res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of
    // [n * (n-1) *---* (n-k+1)] / 
    // [k * (k-1) *---* 1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Function to return the number of paths
ll countPaths(int x1, int y1, int x2, int y2)
{
 
    // Difference between the 'x' 
    // coordinates of the given points
    int m = abs(x1 - x2);
 
    // Difference between the 'y' 
    // coordinates of the given points
    int n = abs(y1 - y2);
 
    return (binomialCoeff(m + n, n));
}
 
// Driver code
int main()
{
    int x1 = 2, y1 = 3, x2 = 4, y2 = 5;
    cout << countPaths(x1, y1, x2, y2);
    return 0;
}

Java

// Java implementation of the approach 
class GfG 
{
     
//static long ll long long int 
 
// Function to return the value of nCk 
static long binomialCoeff(int n, int k) 
{ 
    long res = 1; 
 
    // Since C(n, k) = C(n, n-k) 
    if (k > n - k) 
        k = n - k; 
 
    // Calculate value of 
    // [n * (n-1) *---* (n-k+1)] / 
    // [k * (k-1) *---* 1] 
    for (int i = 0; i < k; ++i)
    { 
        res *= (n - i); 
        res /= (i + 1); 
    } 
 
    return res; 
} 
 
// Function to return the number of paths 
static long countPaths(int x1, int y1, int x2, int y2) 
{ 
 
    // Difference between the 'x' 
    // coordinates of the given points 
    int m = Math.abs(x1 - x2); 
 
    // Difference between the 'y' 
    // coordinates of the given points 
    int n = Math.abs(y1 - y2); 
 
    return (binomialCoeff(m + n, n)); 
} 
 
// Driver code 
public static void main(String[] args) 
{ 
    int x1 = 2, y1 = 3, x2 = 4, y2 = 5; 
    System.out.println(countPaths(x1, y1, x2, y2)); 
}
} 
 
// This code is contributed by 
// Prerna Saini.

Python3

# Python3 implementation of the approach
 
# Function to return the value of nCk
def binomialCoeff(n, k):
 
    res = 1
 
    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k
 
    # Calculate value of
    # [n * (n-1) *---* (n-k+1)] / 
    # [k * (k-1) *---* 1]
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
 
    return res
 
# Function to return the number
# of paths
def countPaths(x1, y1, x2, y2):
 
    # Difference between the 'x' 
    # coordinates of the given points
    m = abs(x1 - x2)
 
    # Difference between the 'y' 
    # coordinates of the given points
    n = abs(y1 - y2)
 
    return (binomialCoeff(m + n, n))
 
# Driver code
x1, y1, x2, y2 = 2, 3, 4, 5
print(countPaths(x1, y1, x2, y2))
 
# This code is contributed 
# by Mohit Kumar

C#

// C# implementation of the approach 
using System;
 
class GFG 
{
 
// Function to return the value of nCk 
static long binomialCoeff(int n, int k) 
{ 
    long res = 1; 
 
    // Since C(n, k) = C(n, n-k) 
    if (k > n - k) 
        k = n - k; 
 
    // Calculate value of 
    // [n * (n-1) *---* (n-k+1)] / 
    // [k * (k-1) *---* 1] 
    for (int i = 0; i < k; ++i)
    { 
        res *= (n - i); 
        res /= (i + 1); 
    } 
 
    return res; 
} 
 
// Function to return the number of paths 
static long countPaths(int x1, int y1,
                       int x2, int y2) 
{ 
 
    // Difference between the 'x' 
    // coordinates of the given points 
    int m = Math.Abs(x1 - x2); 
 
    // Difference between the 'y' 
    // coordinates of the given points 
    int n = Math.Abs(y1 - y2); 
 
    return (binomialCoeff(m + n, n)); 
} 
 
// Driver code 
public static void Main() 
{ 
    int x1 = 2, y1 = 3, x2 = 4, y2 = 5; 
    Console.Write(countPaths(x1, y1, x2, y2)); 
}
} 
 
// This code is contributed by 
// Akanksha Rai

PHP

<?php
// PHP implementation of the approach 
//static long ll long long int 
 
// Function to return the value of nCk 
function binomialCoeff($n, $k) 
{ 
    $res = 1; 
 
    // Since C(n, k) = C(n, n-k) 
    if ($k > $n - $k) 
        $k = $n - $k; 
 
    // Calculate value of 
    // [n * (n-1) *---* (n-k+1)] / 
    // [k * (k-1) *---* 1] 
    for ($i = 0; $i < $k; ++$i)
    { 
        $res *= ($n - $i); 
        $res /= ($i + 1); 
    } 
 
    return $res; 
} 
 
// Function to return the number of paths 
function countPaths($x1, $y1, $x2, $y2) 
{ 
 
    // Difference between the 'x' 
    // coordinates of the given points 
    $m =abs($x1 - $x2); 
 
    // Difference between the 'y' 
    // coordinates of the given points 
    $n = abs($y1 - $y2); 
 
    return (binomialCoeff($m + $n, $n)); 
} 
 
// Driver code 
{ 
    $x1 = 2; $y1 = 3; $x2 = 4; $y2 = 5; 
    echo(countPaths($x1, $y1, $x2, $y2)); 
}
 
// This code is contributed by 
// Code_Mech.

Javascript

<script>
 
// javascript implementation of the approach
 
// Function to return the value of nCk
function binomialCoeff(n, k)
{
    var res = 1;
    var i;
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of
    // [n * (n-1) *---* (n-k+1)] / 
    // [k * (k-1) *---* 1]
    for (i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Function to return the number of paths
function countPaths(x1, y1, x2, y2)
{
 
    // Difference between the 'x' 
    // coordinates of the given points
    var m = Math.abs(x1 - x2);
 
    // Difference between the 'y' 
    // coordinates of the given points
    var n = Math.abs(y1 - y2);
 
    return (binomialCoeff(m + n, n));
}
 
// Driver code
    var x1 = 2, y1 = 3, x2 = 4, y2 = 5;
    document.write(countPaths(x1, y1, x2, y2));
 
</script>

Output:

Time complexity: O(k) where k=abs(y1 – y2)

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!