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. ​ 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.  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.  ## Combined Form

Max_Value(1,n) = Maximum {coin + 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 Implementationdef 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[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:

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:

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:

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, which is the answer!

RELATED TAGS

coin in a line
coins 