Last Updated: 3 Dec, 2020
Coin Game
Easy
Asked in companies
Wong is hungry and wants to eat tuna melt. He checks his pocket and finds that he has only a buck left. He asked Dr. Strange to lend him some money, for which Strange agrees but to get the money, Wong has to beat Strange in a game of coins. The game will be played by two players. Being kind enough Strange allows Wong to play first. Now, Strange arranges N coins in a row. Each coin is associated with a value. In his turn, every player can remove only one coin from either end. Once a player removes a coin, it can not be placed back into the row. At the end when all coins are removed, the player with the maximum value of coins wins. Wong will only get money if he wins the game. Wong knows that he can not beat sorcerer supreme, so he asked for your help.
You are given an array of integers, say, ‘ARR’ of size ‘N’ containing the values associated with ‘N’ coins. Your task is to determine the maximum value of coins you can obtain by following two rules:
a) Both players play in alternate turns and they can remove only one coin in their turn.
b) Any player can remove coins only from either of the two ends of ‘ARR’.
Note:
There can be more than one set of coins with maximum value.
For example:
a) Consider 3 coins are placed with values [10, 20, 30]: Wong removes 30, then Strange removes 20, then Wong removes 10. Now all coins are taken, and Wong has coins with value 40 and he wins.
b) Consider 1 coin is placed with value [100]: Wong removes the coin and no other coin is left. So, Wong wins with value 100.
Note:
a) The game only ends when NO MORE COIN IS LEFT to play with.
b) If a game ends in a draw, Wong is declared the winner.
Input Format :
The first line of input contains an integer 'T', which denotes the number of the test cases. Then the test case follows.
The first line of every test case contains an integer ‘N’ representing the size of the array.
The second line of every test case contains ‘N’ single space-separated integers representing the array elements.
Output Format :
For each test case, print a single integer representing the maximum value of coins you can get for a winning case.
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 <= 5
1 <= N <= 10 ^ 3
1 <= ARR[i] <= 10 ^ 7
Where ‘ARR[ i ]’ denotes the value for ‘ith’ element of the array ‘ARR’.
Time Limit: 1 sec.
Approaches
The idea is to check each element from the array ‘ARR’ recursively whether including it in the result will give us the maximum sum or not.
Approach :
First, we will define a recursive function, say ‘MAXCOINS’ that accepts as parameters, an array of integers ‘ARR’, iterator pointer ‘STARTINDEX’ which will iterate throughout the ‘ARR’, iterator pointer ‘ENDINDEX’ which will iterate from the last element of ‘ARR’ till ‘STARTINDEX’ + 1 and ‘SUM’ which will contain the sum of the values of ‘ARR’ and do:
- Check if ‘ENDINDEX’ = ‘STARTINDEX’ + 1 i.e. only two elements are left. Return maximum of ‘ARR[STARTINDEX]’ and ‘ARR[ENDINDEX]’.
- Case1 - when you consider picking up the coin from the first index. Call function ‘MAXCOINS’ for ‘ARR’, ‘STARTINDEX’ + 1, ‘ENDINDEX’, and ‘SUM’ - ‘ARR[STARTINDEX]’ and subtract the value returned by it from SUM, say the value obtained is stored in a variable ‘VAL1’.
- Case2 - when you consider picking up the coin from the end index. Call function ‘MAXCOINS’ for ‘ARR’, ‘STARTINDEX’, ‘ENDINDEX’ - 1 and ‘SUM’ - ‘ARR[ENDINDEX]’ and subtract the value returned by it from ‘SUM’, say value obtained is stored in a variable ‘VAL2’.
- Return MAX of VAL1 and VAL2.
We can reduce the steps involved in the recursive approach by storing the result for every solved subproblem. We will define a function ‘MAXCOINS’ that accepts parameters, an array of integers ‘ARR’, iterator pointer ‘STARTINDEX’ which will iterate throughout the ‘ARR’, iterator pointer ‘ENDINDEX’ which will iterate from the last element of ‘ARR’ till ‘STARINDEX’ + 1 , 2D array of integers initialised to -1, say ‘MEMO’ and an integer ‘SUM’ that contains the sum of all values in ‘ARR’.
From the figure we can see the recursion tree for array ‘COINS’ = [5, 1, 3, 2, 4].
In the first level of the recursion tree - On the left side, Wong takes the coin with value 5 and Stranger left with the array [1, 3, 2, 4]. On the right side, Wong takes the coin with value 4 and Stranger left with the array [5, 1, 3, 2, 4].
In the next level of the recursion tree - Stranger takes the coin with largest value from both the ends and hence, Wong left with the array [1,3, 2].
We can see the recurring subproblems marked with a circle.
Approach :
- Check if ‘ENDINDEX’ = ‘STARTINDEX’ + 1 i.e. only two elements are left. Return maximum of ‘ARR[STARTINDEX]’ and ‘ARR[ENDINDEX]’.
- If ‘MEMO[STARTINDEX][ENDINDEX]’ is not -1, then return ‘MEMO[STARTINDEX][ENDINDEX]’.
- The case when you consider picking up the coin from the first index. Call function ‘MAXCOINS’ for ‘ARR’, ‘STARTINDEX’ + 1, ‘ENDINDEX’, ‘MEMO’ and ‘SUM-ARR[STARTINDEX]’ and subtract the value returned by it from SUM, say value obtained is stored in a variable ‘VAL1’.
- The case when you consider picking up the coin from the end index. Call function ‘MAXCOINS’ for ‘ARR’, ‘STARTINDEX’, ‘ENDINDEX’ - 1, ‘MEMO’ and ‘SUM-ARR[ENDINDEX]’ and subtract the value returned by it from ‘SUM’, say value obtained is stored in a variable ‘VAL2’.
- Update ‘MEMO[STARTINDEX][ENDINDEX]’ by maximum of ‘VAL1’ and ‘VAL2’.
Both Wong and Dr Strange are equally good. So, both of them will try to choose the best option available to them. Consider ‘ith’ and ‘jth’ coins are available to be drawn. This leaves them with two choices:
Wong chooses the ‘ith’ coin with let’s say with the value ‘Vi’: Then Dr Strange can either choose (i+1)th coin or ‘jth’ coin in a way that he leaves Wong with minimum value.
That means Wong can collect the value ‘Vi’ + minimum from (‘MAXCOINS(i+2, j)’, ‘MAXCOINS(i+1, j-1)’).
Wong chooses the ‘jth’ coin with value ‘Vj’: Then Dr Strange can either choose 'ith' coin or '(j-1) th' coin in a way that leaves Wong with minimum value.
That means Wong can collect the value ‘Vj’ + minimum value from (‘MAXCOINS(i+1, j-1)’, ‘MAXCOINS(i, j-2)’).
Now, if we consider ‘MAXCOINS(i,j)’ representing the maximum value Wong can collect from ‘ith’ coin to ‘jth’ coin, then:
‘MAXCOINS(i, j)’ = maximum(‘Vi’ + minimum (‘MAXCOINS(i+2, j)’, ‘MAXCOINS(i+1, j-1)’ ), minimum (‘MAXCOINS(i+1, j-1)’, ‘MAXCOINS(i, j-2)’ ) )
where, ‘MAXCOINS(i, j)’ = ‘Vi’, when ‘j’ = ‘i’ i.e. only one coin is left or ‘MAXCOINS(i, j)’ = maximum(‘Vi’, ‘Vj’) when ‘j’ = ‘i’ + 1 i.e. only two coins left.
We can implement this using dynamic programming. We define a function that accepts as parameters, an array of integers ‘ARR’ and an integer ‘N’ representing length of ‘ARR’.
Approach :
- Define a 2D array of integers ‘DP’ of size ‘N’ x ‘N’ to store the value of ‘MAXCOINS(i,j)’.
- Define variables 'WINDOW', ‘i’ and ‘j’ to iterate over ‘DP[][]’. ‘X’, ‘Y’, ‘Z’, ‘VAL1’ and ‘VAL2’ to help in calculating the result.
- Iterate for 0 <= 'WINDOW' < ‘N’ and do:
- Initialize ‘i’ to 0 and iterate for 'WINDOW' <= ‘j’ < ‘N’ and do:
- We first find the maximum value that can be obtained if Wong picks ‘ith’ coin and Strange pick ‘(i+1)th’ coin and store it in ‘X’. So, we check if ‘i’ + 2 <= ‘j’. If yes, assign DP[i + 2][j] to ‘X’ else 0.
- Then we find the maximum value that can be obtained if Wong picks ‘ith’ coin and Strange picks ‘jth’ coin and stores it in ‘Y’. So, we check if ‘i’ + 1 <= ‘j’ - 1. If yes, assign DP[i + 1][j - 1] to ‘Y’ else 0.
- Then we find the maximum value that can be obtained if Wong picks ‘jth’ coin and Strange picks ‘(j-1)th’ coin and stores it in ‘Z’. So, we check if ‘i’ <= ‘j’ - 2. If yes, assign DP[i][j-2] to ‘Z’ else 0.
- Store minimum of ‘X’ and ‘Y’ + ‘ARR[i]’ in ‘VAL1’. This is the case when we are considering that Wong picked 'ith' element.
- Store minimum of ‘Y’ and ‘Z’ + ‘ARR[j]’ in ‘VAL2’. This is the case when we are considering that Wong picked the ‘jth’ element.
- Store maximum of ‘VAL1’ and ‘VAL2’ in ‘DP[i][j]’.
- Return ‘DP[0][N-1]’.