Link copied to clipboard. Share away!

Dismiss

Published on 10 Mar 2020

Two player coin game using Dynamic Programming is discussed here.

There is an array of coins with different worth. Two players playing this game can pick a coin from either of the left or right end. The player with maximum sum will win. Both players are optimally playing the game.

If player one wins the game print PLAYER 1 WINS else if player 2 wins print PLAYER 2 WINS if they both have equal sum at the end, print DRAW.

**Strategy 1:**

**Array = {18, 20, 15, 30, 10, 14 }**

Player 1 picks 18, now the array of coins is

**20 15 30 10 14**

Player 2 picks 20, now the array of coins is

**15 30 10 14**

Player 1 picks 15, now the array of coins is

**30 10 14**

Player 2 picks 30, now the array of coins is

**10, 14**

Player 1 picks 14, now the array of coins is

**10**

Player 2 picks 10.

The total value of coins picked by the second player is more **(20 + 30 + 10)** compared to the first player **(18 + 15 + 14)**.

So, the second player wins.

Having made the first move, the first player is unable to succeed. So,should we make the first move or not? Does it matter?

Playing first will guarantee that the player will not lose or at least end up with a draw game. Now, consider the strategy 2 using a dynamic programming approach.

**Strategy 2:**

- Count the sum of all coins that are odd-numbered. (Let the odd-numbered coins be X)
- Count the sum of all coins that are even-numbered. (Let the even-numbered coins be Y)
- If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
- If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
- If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.

Considering the same example,

Array = {18, 20, 15, 30, 10, 14}

- Sum of odd coins = 18 + 15 + 10 = 43
- Sum of even coins = 20 + 30 + 14 = 64

Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked by the other player, the first player again gets an opportunity to pick an even coin and block all even coins.

C++

Output

Input -
5
2 1 2 1 2
Output -
DRAW

**Test Case 1**

I/P

5

2 1 2 1 2

O/P

DRAW

**Test Case 2**

I/P

10

14 26 10 13 24 14 17 30 21 24

O/P

PLAYER 1 WINS

**Test Case 3**

I/P

5

1 36 41 20 5

O/P

PLAYER 2 WINS

**Test Case 4**

I/P

6

2 2 2 2 2 2

O/P

DRAW

**Test Case 5**

I/P

3

21 150 34

O/P

PLAYER 2 WINS

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×