Can you help me understand the problem statement

help
1

I read this problem but couln’t get which path is he talking about.

https://www.interviewbit.com/problems/count-of-paths-in-a-grid/

    00   | 01
    ----------    
    10   |  11

So for grid size 2X2, how total number of path from 00 to 11 is 1?

2

no, i think it should be 2,as its mentioned in the question that path shouldn`t cross major diagonal but can overlap with. basically count no. of ways of reaching (a,a) but all path should either lie on upper triangle matrix or lower triangle matrix divided by major diagonal.

1 Like
3

Let’s consider i as row and j as column.

Now, the question is saying that we have to consider the path only if i >= j.
That means, anytime you encounter the colnum( j ) is exceeding the rownum( i ), you need to step back.

You can consider this recursive approach:

bool isSafe(int i, int j, int n) {
    return i >= 1 and j >= 1 and i <= n and j <= n;
}

int countPath(int i, int j, int n) {
    if(!isSafe(i, j, n)) {
        return 0;
    }
    if(i == n and j == n) {
        return 1;
    }
    if(i < j) {
        return 0;
    }
    return countPath(i + 1, j, n) + countPath(i, j + 1, n);
}

int solve(int n)
{
    if(n == 1) {
        return 1;
    }
    return countPath(1, 1, n);
}

Here, we are only considering the path if i >= j.

But as this approach is exponential, it will not be going to work for n >= 18.

Well, if you will generate the result for first 10 (let say n = 10) then you will see that the sequence is nothing but the Catalan Number.

So for that, you might consider the below code.

long int mod = 1e9 + 7;

long int getCount(int n) 
{
    long int dp[n + 1]; 
    dp[0] = dp[1] = 1; 
    for (int i = 2; i <= n; i++) { 
        dp[i] = 0;
        for (int j = 0; j < i; j++) { 
            dp[i] = (dp[i] % mod + (dp[j] % mod * dp[i-j-1] % mod) % mod) % mod; 
        }
    }
    return dp[n];
} 

int Solution::solve(int n)
{
    return getCount(n - 1);
}

Hope it helped…
Happy Coding!

1 Like