Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

coin in a line
coins

What is the coin in a line problem?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

In the coin in a line problem, two players are given an even number of coins in a single row. The players take turns alternatively. For each turn, a player selects a coin from either the beginning or the end of the row. The player with the maximum total value wins. ​

svg viewer

So, the goal is to provide a strategy in which the player with the first move gets the maximum value coins in the end.

There is an even amount of coins (i.e., 1 to n ) and the two players take their turns alternatively.

If player1 picks the coin at position 1, then player2 (who is equally clever) will pick up a coin and leave player1 with the less valuable coin.

svg viewer
svg viewer

If player1 picks the coin at position n, then player2 (who is equally clever) will pick up a coin, and leave player1​ with the less valuable coin.

svg viewer
svg viewer

Combined Form

Max_Value(1,n) = Maximum {coin[1] + Minimum{Max_Value(3,n),
Max_Value(2,n-1)} , coin[n] +
Minimum{Max_Value(2,n-1),Max_Value(1,n-2)}};

Code

# Python Implementation
def Coin_in_a_line(arr, n):
# Creating a table to store max value.
Max_Value = [[0 for i in range(n)]
for i in range(n)]
# Fill the table using the above method.
for k in range(n):
for j in range(k, n):
i = j - k
x = 0
if((i + 2) <= j):
x = Max_Value[i + 2][j]
y = 0
if((i + 1) <= (j - 1)):
y = Max_Value[i + 1][j - 1]
z = 0
if(i <= (j - 2)):
z = Max_Value[i][j - 2]
Max_Value[i][j] = max(arr[i] + min(x, y),
arr[j] + min(y, z))
return Max_Value[0][n - 1]
# Sample code
arr = [ 5, 16, 3, 7 ]
print(Coin_in_a_line(arr, 4))

This problem can be solved most efficiently by dynamic programming. The main logic behind the code is explained best by the Max_Value array:

0123 0123

The row number specifies the starting position and the column number specifies the ending position within the coin line. We must pick a coin at either end of this range. So, Max_Value[i][j] would mean the range from i to j.

In the code, k is the interval or window. The base case is when k is 0 or i = j. This means that there is only one coin to choose. Hence, the diagonal of the array will be filled first:

0123 051162337

Next, the interval is 1, meaning there are 2 choices to pick from, namely arr[i] or arr[j]. We must pick the maximum between these two. These values are filled out in the array:

0123 05116162163377

Now, the interval is 2 or larger. There are a few possible scenarios we need to cover. At the start, we can pick either arr[i] (first) or arr[j] (last).

If we pick the first value, our opponent can choose either arr[i+1] or arr[j].

  • If they pick arr[i+1], our next choice will be arr[i+2] or arr[j]. But since we built up from the base case, we already have the max value for this in Max_Value[i+2][j]! We will store this in x.
  • If they pick arr[j], our next choice will be arr[i+1] or arr[j-1]. This can be found in Max_Value[i+1][j-1]. We will store this in y.

So, for this scenario, what we have as our choice of moves is:

arr[i] + min(x, y)

If we pick the last value, our opponent can choose either arr[i] or arr[j-1].

  • If they pick arr[i], our next choice will be arr[i+1] or arr[j-1]. This can be found in Max_Value[i+1][j-1]. Like before, we will store this in y.
  • If they pick arr[j-1], our next choice will be arr[i] or arr[j-2]. This can be found in Max_Value[i][j-2]. We will store this in z.

So, for this scenario, what we have as our choice of moves is:

arr[j] + min(y, z)

Lastly, we must take the maximum out of these two scenarios:

max(arr[i] + min(x, y), arr[j] + min(y, z))

This will help us find Max_Value[0][3], which is the answer!

0123 0511616281633231977

RELATED TAGS

coin in a line
coins
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring