N Coins in a Row Game (Pots of Gold interview problem) optimal solution in O(n)
We’ll present 3 different solutions. The first one relies on nothing more than just logical reasoning and requires no computer science background whatsoever. The second solution is based on a recursive function that makes use of memorization technique and has order n-squared running time. Finally, we’ll go over an algorithm that finds an optimal solution and runs in linear time.
The game is played as follows: some number of coins, of various denominations, are arranged in a line. Two players take turns at removing a coin from either end of the line. They are free to choose which end of the line to take a coin from, but taking a coin from the middle is not allowed. The winner of the game is the player who collects the most amount of money.
The O(n) optimal solution algorithm was discovered by a Polish computer scientist, Tomasz Idziaszek. Here is his paper
https://www.mimuw.edu.pl/~idziaszek/t...
Mathematical Puzzles: A Connoisseur's Collection, by Peter Winkler:
https://www.amazon.com/dp/1568812019/
Full Java source code of N Coins in a Row, also called Pots of Gold Problem, implementation of linear time algorithm:
https://bitbucket.org/StableSort/play...
Written and narrated by Andre Violentyev