# 22. Number of Paths

The problem can be found at the following link: [Question Link](https://practice.geeksforgeeks.org/problems/number-of-paths0926/1)

![](https://badgen.net/badge/Level/Medium/yellow)

## My Approach

The problem statement implies that this question is simple DP, but due to the constraints, it requires a highly optimized solution, which is not intuitive. At first, I also did not get the answer. But through internet get help to find a solution.

To solve this problem, I used a combination formula to calculate the number of paths from the top-left corner to the bottom-right corner of an MxN grid.

* I start iteration through the rows of the grid, and for each row, I calculate the [binomial coefficient](https://cp-algorithms.com/combinatorics/binomial-coefficients.html) (n choose k), where n is the sum of the row and column indices, and k is the row index. I used modular arithmetic to handle large numbers.

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(M)`, where `M` and `N` are the dimensions of the grid.
* **Auxiliary Space Complexity**: `O(1)`. We only use a constant amount of extra space.

## Code (C++)

```cpp
class Solution {
public:
    int mod = 1e9 + 7;

    long long modInv(long long a, long long b) {
        return 1 < a ? b - modInv(b % a, a) * b / a : 1;
    }

    long long numberOfPaths(int m, int n) {
        long long out = 1;

        for (int i = 0; i < m - 1; i++) {
            long long inverse = modInv(i + 1, mod);
            out = (out * (i + n)) % mod;
            out = (out * inverse) % mod;
        }

        return out;
    }
};
```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://github.com/getlost01/gfg-potd/discussions). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the [getlost01/gfg-potd](https://github.com/getlost01/gfg-potd) repository.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gl01.gitbook.io/gfg-editorials/2023/10-2023-oct-21/22-number-of-paths.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.