Problem

Submissions

Hints & solutions

Discuss

Lakshay and Manik

Moderate

0/80

Contributed by

1 upvote

Asked in company

Problem statement

Lakshay and Manik met on an online chatting platform. Due to their shared interest in problem-solving, they became good friends. One day Lakshay decided to meet Manik. Manik lives in a small town at (0, N - 1) on a square matrix of N * N, and Lakshay lives at (N - 1, 0). As they are fond of problem-solving, Manik wants to know how many ways Lakshay can reach him. Help Lakshay to find out how many possible paths are there to reach Manik.

Lakshay can move Up(j, k) -> (j - 1, k), RIght(j, k) -> (j, k + 1) or Up-Right(j, k) -> (j - 1, k + 1).

Answers can be very large, so return the answer modulo 1000000007.

For Example :

N = 2

For n = 2, there can be three possible moves, as shown in the figure. Hence the answer is 3.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the size of the square matrix.

Output Format :

For each test case, print a single integer “ans” denoting the total number of paths.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10    
1 <= N <= 500

Time limit: 1 sec

Sample Input 1 :

2
3
2

Sample Output 1 :

13
3

Explanation For Sample Input 1 :

In the first test case, There is a total of thirteen possible paths. Hence, the answer is 13.

In the second test case, There is a total of 3 possible paths. Hence, the answer is 3.

Sample Input 2 :

2
5
7

Sample Output 2 :

321
8989

Hint 1

Hint 2

Hint 3

Recursively call all the possible paths and return the final answer.

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursion

In this approach, we will start from the (N - 1, 0) and add all the possible paths for down, left, and down-left.

The steps are as follows:

In the “main” function:
- Return the function recursion and pass the value of ‘N’ as ‘x’ and one as ‘y’.
In the “recursion” function:
- If x equals to 1 or y equals to N, return 1.
- Else take a variable “ans” to store the answer.
- Update “ans” = (recursion(x - 1, y) + recursion(x, y + 1) + recursion(x - 1, y + 1)) % 1000000007.
- Return “ans”.

Time Complexity

O( 3 ^ N ), where N is the length of the square matrix.

As we are going through all the paths.

Hence the time complexity is O( 3 ^ N ).

Space Complexity

O( 1 )

No extra space is used.

Hence the space complexity is O(1).

(100% EXP penalty)

Lakshay and Manik

Console