You are given two positive integers x and y, denoting the number of coins with values 75 and 10 respectively.
Alice and Bob are playing a game. Each turn, starting with Alice, the player must pick up coins with a total value 115. If the player is unable to do so, they lose the game.
Return the name of the player who wins the game if both players play optimally.
Example 1:
Input: x = 2, y = 7
Output: "Alice"
Explanation:
The game ends in a single turn:
Example 2:
Input: x = 4, y = 11
Output: "Bob"
Explanation:
The game ends in 2 turns:
Constraints:
1 <= x, y <= 100Problem 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.
The crucial part of the problem is ensuring a player can pick coins totaling 115 on each turn. A greedy approach can be useful, where we first attempt to use as many 75-value coins as needed, and then adjust with 10-value coins if possible.
For each turn, check if it's possible to pick coins to make 115. If the current player can't make a move, they lose the game. Start with the optimal strategy for Alice using available coins with the highest value first (75-value coins).
The C program utilizes a greedy approach to check the possibility of forming 115 using the given coins. Starting with one 75 coin and four 10 coins, it continuously checks if this combination can be used; otherwise, it attempts to use 11 coins of 10-value to form the required sum. The condition to switch between players (Alice and Bob) is achieved by a loop until no valid combinations are available.
Both the time and space complexities for this implementation are O(1), given that it involves a constant number of operations based on fixed maximum values of x and y defined by the constraints.
Instead of a greedy approach, this simulation method iteratively reflects each player's move, step-by-step adjusting coins down in realistic gameplay. Each turn is evaluated in depth for potential coin uses, ensuring the players toggle turns by confirming progress within permissible moves made by previous players.
Each move by Alice and Bob factors in various combinations to make a sum with available coins and determines if progress is possible. A general game simulation allows understanding of transition from one turn to the next when playing optimally, and chiseling down until one player can no longer form 115.
The simulation-based solution tracks game state iteratively with an alternating turn switch between Alice and Bob every successful move. Each player's available coins are balanced with potential moves to calculate feasible pairs and win conditions. Once possibilities exhaust, the last turn taken defines the winner, transferring control of flow using bitwise toggles.
Fixed constraints limitations yield: Time complexity: O(1).
Space complexity: O(1).
Since each round of operation consumes 2 coins valued at 75 and 8 coins valued at 10, we can calculate the number of rounds k = min(x / 2, y / 8), and then update the values of x and y, where x and y are the remaining number of coins after k rounds of operations.
If x > 0 and y geq 4, then Alice can continue the operation, and Bob loses, return "Alice"; otherwise, return "Bob".
The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Both the time and space complexities for this implementation are O(1), given that it involves a constant number of operations based on fixed maximum values of x and y defined by the constraints. |
| Simulation Approach | Fixed constraints limitations yield: Time complexity: O(1). |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation | O(k) | O(1) | When modeling the game step-by-step to understand turn mechanics |
| Greedy / Mathematical Insight | O(1) | O(1) | Best choice when each move consumes fixed resources and total moves can be computed directly |
3222. Find the Winning Player in Coin Game (Leetcode Easy) • Programming Live with Larry • 493 views views
Watch 8 more video solutions →Practice Find the Winning Player in Coin Game with our built-in code editor and test cases.
Practice on FleetCode