Path with K Coins

Hard
0/120
Average time to solve is 45m
profile
Contributed by
4 upvotes
Asked in companies
SAP LabsD.E.ShawCodenation

Problem statement

The Ultimate Ninja Ankush is playing a game where he has a grid of ‘N’ * ‘M’ size and each block of the grid has some coins. The Ultimate Ninja ankush is carrying a knapsack that can fit only ‘K’ coins, and since he is very greedy, he wants to know the number of paths where he can collect exactly ‘K’ coins. He is initially at the top-left and wants to reach bottom-right

More formally, return the number of paths whose total sum of coins is equal to ‘K’ from 0,0 to ‘N - 1’, ‘M - 1’.

Note: 
Since the answer can be very large print the answer modulo 10 ^ 9 + 7.

For example

Given:
‘N’ = 3, ‘M’ = 3
‘Grid[][]’ = [[5, 2, 5],
              [3, 3, 1],
              [3, 5, 1]]
‘K’ = 14.
The answer will be 1, since There is only 1 path that is from (0,0) to (0,1) to (0,2) to (1,2) to (2,2) this is because 5 + 2 + 5 + 1 + 1 = 14
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M,’ where ‘M’ is the number of rows in ‘SEATS’ and ‘N’ where ‘N’ is the number of columns in ‘GRID’.

The next ‘M’ lines of each test case contains ‘N’ space-separated integers, which denotes the number of coins at each point.

The next line of each test case contains a single integer ‘K’.
Output Format : 
For each test case, You are supposed to return an integer that denotes the total number of paths with the sum of coins equal to ‘K’.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 20
1 <= ‘M’ <= 20
0 <= ‘K’ <= 1000

Time Limit: 1sec.

Sample Input 1 :

2
3 3
5 2 5
3 3 1
3 5 1
14
2 3 
1 2 1
2 2 1
6

Sample Output 1 :

1
2

Explanation of the Sample Input 1:

In the first test case, The answer will be 1, since There is only 1 path that is from (0,0) to (0,1) to (0,2) to (1,2) to (2,2) this is because 5 + 2 + 5 + 1 + 1 = 14

In the second test case, The answer will be 2, since there are 2 paths those are (0,0) to (1,0) to (1,1) to (1,2) and (0,0) to (0,1) to (1,1) to (1,2) and 1 + 2 + 2 + 1 = 6 in both cases.

Sample Input 2 :

2
3 3
1 2 3
4 5 6
1 2 3
11
2 2
1 1
1 1
3

Sample Output 2 :

3
2
Hint

Can we check all paths using recursion?

Approaches (2)
Using Recursion

The idea is to recursively travel all paths and calculate which path’s total sum of coins is equal to ‘K’.


 

The steps are as follows:

  • We will use a helper function ‘pathWithKCoinsHelper’ which takes ‘grid’, ‘row’, ‘col’ , ‘myCoins’, and ‘K’ as input parameters and returns the number of paths that exist such that the sum of coins equal ‘K’, Initially ‘row’ and ‘col’, and ‘myCoins’ are 0.
    • The base condition would be to check if we are at the last cell and if ‘myCoins’ is equal to ‘K’. If they are, return 1, indicating that we found a valid path.
    • If we are out of bounds or ‘myCoins’ is greater than ‘K’, return 0, indicating that we did not find a valid path.
    • Recur for ‘row + 1’, and ‘myCoins + grid[row][col]’ and store it in a variable ‘moveForward’ which denotes the number of valid paths if we move forward.
  • Similarly, recur for ‘col + 1’ and ‘myCoins + grid[row][col]’ and store it in a variable ‘moveDown’, which denotes the number of valid paths if we move down.
  • Return the final answer as the sum of ‘moveDown’ and ‘moveForward’, which denotes the total number of valid paths if we moved in the downward direction or in the forward direction.
Time Complexity

O((2 ^ M) * (2 ^ N)), Where ‘M’ is the number of rows, and ‘N’ is the number of columns.


 

Since we are trying all possible paths, the overall time complexity will be O(2 ^ N * 2 ^ M). 

Space Complexity

O(N * M * K), Where ‘M’ is the number of rows, and ‘N’ is the number of columns.


 

Since we are using recursion, the call stack made would be of the height N * M *K. Therefore the overall space complexity will be O(N * M * K).

Code Solution
(100% EXP penalty)
Path with K Coins
Full screen
Console