K Turns Allowed

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in companies
AmazonSalesforceZepto

Problem statement

Ninja has been given the dimensions of a matrix, count the number of paths to reach the bottom right from top left with maximum k turns allowed.

A valid turn :

There are two possible scenarios when a turn can occur at point (i, j):

Turns Right: (i - 1, j)  ->  (i, j)  ->  (i, j + 1)

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains three space-separated integers ‘N’, ’M’, and ‘K’ denoting the number of rows, columns, and maximum turn around respectively.
Output Format: 
For each case, we need to print the total number of possible paths % (10 ^ 9 + 7).
Note: 
The answer should be in the mod(10 ^ 9 + 7)

The output of each test case will be printed in a separate line.
Note: 
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100

Time limit: 1 sec.
Sample Input 1:
1 
3 3 2
Sample Output 1:
4
Explanation of Sample Input 1:
Test case 1:
For the first test case of sample output 1, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 2 ways
Hence our answer shall be 4
Sample Input 2:
2 
4 5 3
2 3 4
Sample Output 2:
19
3
Explanation of Sample Input 2:
Test case 1:
For the first test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 5 ways
3 turns -> 12 ways
Hence our answer shall be 19

Test case 2:
For the second test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 1 ways
Hence our answer shall be 3.
Hint

Recursively design a function that returns the number of paths from that location.

Approaches (2)
Brute Force Approach

Here, we will use basic recursion to calculate the number of the unique paths with ‘K’ most turns around. We can declare a function having 4 parameters as ith row index, jth row index, remaining k turns possible from that index(K), and the direction of the movement (d). For row, we consider ‘d’ equal to ‘0’ and, for column ‘d’ is equal to ‘1’. Using the recursive function we shall call the function for both adjacent cells (right cell and bottom cell), and add them up and return to the parent function. Inside our recursive function, firstly we need to have certain base conditions.

Our base conditions will into the following constraints:

  • If our current row index and column index becomes negative, we can return 0 as failure
  • If we reach the final bottom right point, we will return 1 as success.
  • If ‘K’ is equal to zero indicating no further turns:
    • If we are in the last row and our current direction is 0, then we can return 1 as a success
    • If we are in the last column and our current direction is 1, then we can return 1 as a success
    • Otherwise, we can return zero as a failure.

Now we can compute for both the directions separately looking into the current movement pattern and return to the parent function.

For each arithmetic operation, we need to use the mod ( 10 ^ 9 + 7). 

 

Algorithm:

 

  • From the main function, call the recursive function (‘countPath’) for the adjacent cells as ‘countPath(N - 2, M - 1, K, 1)’ and ‘countPath(N - 1, M - 2, K, 0)’, sum them up and return to the main function.
  • In our recursive function, we have 4 parameters as ‘i-th’ row index, ‘j-th’ row index, ‘k-th’ turn possible, and direction of movement (‘d’).
  • If our current row index and column index becomes invalid, we can return 0 as a failure.
  • If we reach the final bottom right point, we will return 1 as success.
  • If ‘K’ is equal to zero indicating no further turns:
    • If we are in the last row and our current direction is 0, then we can return 1 as a success
    • If we are in the last column and our current direction is 1, then we can return 1 as a success
    • Otherwise, we can return zero as a failure.
  • If our current direction is 0,
    • Return the summation of ‘countPath( ‘i’, ‘j’ - 1, ‘k’, ‘d’)’ + ‘countPath( ‘i’ - 1, ‘j’, ‘k’ - 1, ‘d’ ^ 1)’
  • Otherwise, our current direction is 1,
    • Return the summation of ‘countPath( ‘i’ - 1, ‘j’, ‘k’, ‘d’)’ + ‘countPath( ‘i’, ‘j’ - 1, ‘k’ - 1, ‘d’ ^ 1)’.
  •  
Time Complexity

O(2 ^ (N + M -1)) where N and M are the dimensions of the 2D array given in the input.
 

Here, for every cell, we have 2 possible choices. The total path length from beginning to ending cell is (N+M-1). Hence, our time complexity will be O(2 ^ (N + M - 1)).

Space Complexity

O( N + M - 1) where N and M are the dimensions of the 2D array given in the input.
 

Here, as we are using recursion, we will have a stack that will hold all recursive function calls. Hence, our space complexity will be O( N + M - 1).

Code Solution
(100% EXP penalty)
K Turns Allowed
Full screen
Console