Coins and Rows

Moderate
0/80
0 upvote
Asked in company
Intuit

Problem statement

Ninja and his friend is playing a matrix game in which a matrix having 2 rows and N columns. Each cell of the matrix has some gold coins. Initially, Ninja will start from the cell (1,1) and will move to cell (2, N) which the following moves:

1. Move Right - From cell (i,j) to cell (i,j+1).
2. Move Down - From cell (i,j) to cell (i+1,j).

Ninja will pick the coins from each cell he visits. Now, it’s his friend’s turn. He also performs the moves to reach (2, N) from (1,1). But he can collect only the coins that Ninja hasn’t picked.

The score of the game is the total coins picked by Ninja’s Friend. Ninja will try to minimize the score while his friend will try to maximize the score. Find the score of the game if both the players play optimally.

You are given a matrix ‘M’ of size 2*N. Your task is to find the score of the game if both players play optimally.

For Example 
If the given matrix is ‘M’ = [ [1,3, 9] , [3,5,1 ].The path taken by 
Ninja is 1,3,9,1 and the path taken by his friend is 1,3,5,1. So the total coins picked by his friend is 3+5 =8.
So, the score is 8.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’ denoting the number of columns in the matrix.

The next two lines contain N elements representing row 1 and row 2 of the matrix.
Output Format: 
For each test case, print an integer corresponding to the score of the game if both players play optimally. 

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N<= 10^5.
1 <= M[i][j] <=5 * 10^3.  

Time limit: 1 sec
Sample Input 1:
2
3
1 3 9
3 5 1
3
1 3 7
3 5 1
Sample Output 1:
8
7
Explanation of sample input 1:
For the first test case,

One of the optimal path for Ninja is 1,3,9,1. His friend will follow the path 1,3,5,1 .So the total coins collected by his friend is 3+5 as all other are already collected by Ninja.So the score is 8.Hence,the answer is 8. 

For the second test case:

One of the optimal path for Ninja is 1,3,5,1.His friend will follow the path 1,3,7,1 .So the total coins collected by his friend is 7. So the score is 7. Hence, the answer is 7.
Sample Input 2:
2
4
6 4 6 1 
5 7 8 7 
4
7 7 10 5 
2 7 10 5
Sample Output 2:
7
9
Hint

Try to observe a pattern about the coins left to be collected by the second player.

Approaches (1)
Using Prefix Sum

If we observe a pattern in the path opted by Ninja,the path will be to this type given in the image below.It consist of a prefix of first row and the suffix of second row.


 


 

So,the second player(Ninja’s Friend) have either collect the coins from the suffix of first row or the prefix of the second row.But Ninja is playing first,so will try to pick the coins in such a way that his friends gets the minimum amount of coins.

There can be ‘N’ total different paths that can Ninja opt.So,we will iterate all these paths and find the minimum score his friend can achieve.


 

Algorithm:

  • Declare two integers ‘SUFFIX_SUM’ and ‘PREFIX_SUM’ to store the sum of coins.
  • Set ‘SUFFIX_SUM’ and ‘PREFIX_SUM’ as 0.
  • For i in range 0 to ‘N’-1:
    • Set ‘SUFFIX_SUM’ as ‘SUFFIX_SUM’ + M[0][i].
  • Set ‘ANS’ as INT_MAX.
  • For i in range 0 to ‘N’-1:
    • Set ‘SUFFIX_SUM’ as ‘SUFFIX_SUM’ - M[0][i].
    • ‘SCORE’ is the coin Ninja’s Friend can pick if Ninja switches the row at i’th index.
    • Set ‘SCORE’ as the maximum of ‘PREFIX_SUM’ and ‘SUFFIX_SUM’.
    • Set ‘ANS’ as the minimum of ‘ANS’ and ‘SCORE’.
    • Set ‘PREFIX_SUM’ as ‘PREFIX_SUM’ + M[1][i].
  • ‘ANS’ is the score if both players play optimally.
  • Return ‘ANS’.
Time Complexity

O(N), where ‘N’ is the number of columns in the matrix.

 

In this approach, we are traversing all columns to calculate ‘SUFFIX_SUM’ and calculating minimum score.So the total time is 2*N.Hence the overall time complexity is O(N).

Space Complexity

O(1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Coins and Rows
Full screen
Console