Coin Game

Easy
0/40
Average time to solve is 15m
profile
Contributed by
19 upvotes
Asked in companies
SalesforceOracleD.E.Shaw

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
5 
5 1 3 2 4
5 
6 8 9 2 1
Sample Output 1:
8
16
Explanation for Sample Input 1:
For the First test case, Wong can win by making moves [5, 2, 1].

For the first time Wong will take coin with value ‘5’ from [5, 1, 3, 2, 4]
Then for the next turn Strange will take the coin with value ‘4’ from [1, 3, 2, 4]
Then for the next turn Wong will take the coin with value ‘2’ from [1, 3, 2]
Then Strange will take the coin with value ‘3’ from [1, 3]
At last Wong will take the coin with value ‘1’ from [1]


For the Second test case, Wong can win by making moves [6, 9, 1].

For the first time Wong will take coin with value ‘6’ from [6, 8, 9, 1, 2]
Then for the next turn Strange will take the coin with value ‘8’ from [8, 9, 1, 2]
Then for the next turn Wong will take the coin with value ‘9’ from [9, 1, 2]
Then Strange will take the coin with value ‘2’ from [1, 2]
At last Wong will take the coin with value ‘1’ from [1]
Sample Input 2:
2
3
1 2 3
4 
63 22 56 94
Sample Output 2:
4
150
Hint

Can you think of a Recursive solution?

Approaches (3)
Recursion

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.
Time Complexity

O(2 ^ N), where ‘N’ denotes the number of elements in the array ‘ARR’.


As we are exploring two possible cases for every element of the array. Hence, overall time complexity will be O(2 ^ N).

Space Complexity

O(N), where ‘N’ denotes the number of elements in the array ‘ARR’.

 

As internal call stack will be storing the variables for every call of the function. Hence, overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Coin Game
Full screen
Console