Find the Winning Player in Coin Game - Video Solutions

Problem Overview: Two players take turns performing a fixed operation on two coin piles. Each move removes 1 coin from the first pile and 4 coins from the second pile. The player who cannot make a valid move loses. Given the number of coins in both piles, determine which player wins assuming optimal play.

Approach 1: Simulation (O(k) time, O(1) space)

The most direct way is to simulate the game. As long as the piles allow a move (x >= 1 and y >= 4), subtract 1 from the first pile and 4 from the second. Track whose turn it is and flip the turn after each move. When the loop stops, the player who was supposed to move next loses, so the previous player wins.

This method models the game exactly and is useful for understanding the mechanics. However, the number of iterations equals the number of valid moves. That value can be derived mathematically, which leads to a more efficient approach. This reasoning pattern appears frequently in simulation and simple game theory problems.

Approach 2: Greedy / Mathematical Insight (O(1) time, O(1) space)

Every move always consumes the same resources: 1 coin from pile x and 4 coins from pile y. That means the total number of moves possible in the entire game is limited by whichever pile runs out first. The exact number of valid moves is k = min(x, y // 4).

Once k is known, the winner becomes a simple parity check. Alice starts the game, so if the total number of moves is odd, Alice performs the final move and wins. If the number of moves is even, Bob performs the final move and wins. This converts the problem into a constant-time calculation using basic math reasoning.

This greedy observation removes the need for simulation entirely. Instead of iterating through moves, you directly compute the maximum possible turns and determine which player gets the last one.

Recommended for interviews: The mathematical greedy approach is the expected solution. It demonstrates that you recognized the fixed resource consumption per move and reduced the game to a parity check. Explaining the simulation first shows understanding of the rules, but deriving k = min(x, y // 4) and checking odd/even shows stronger problem-solving skills.