#3222

Easy

LeetCode Problem Workspace

Find the Winning Player in Coin Game

In this game between Alice and Bob, players must pick coins summing to 115. Alice starts, and the goal is to determine the winner if both play optimally.

math simulation game theory

Problem Statement

In the Coin Game, Alice and Bob are playing a game with two types of coins. You are given two integers, x and y, representing the number of 75-value and 10-value coins respectively. Starting with Alice, the players take turns selecting coins summing to 115, using one 75-coin and four 10-coins each turn. The game ends when a player cannot complete their move, meaning they lose.

Your task is to determine which player wins if both play optimally. Return 'Alice' if Alice wins, or 'Bob' if Bob wins. The game is decided by whether players can make the exact sum of 115 on their turn, and this continues until one player cannot play.

Examples

Example 1

Input: x = 2, y = 7

Output: "Alice"

The game ends in a single turn:

Example 2

Input: x = 4, y = 11

Output: "Bob"

The game ends in 2 turns:

Constraints

1 <= x, y <= 100

Solution Approach

Identify Optimal Coin Usage

Since the only way to make 115 is by using one 75-coin and four 10-coins, you need to consider how many turns each player can take based on the given x and y. For each turn, a player needs at least one 75-value coin and four 10-value coins.

Simulate the Game

Simulate the game turn by turn. Alice starts, and then Bob plays, with each player taking one 75-coin and four 10-coins per turn. Deduct these coins from the available supply after each move. Continue until one player cannot make a valid move.

Determine the Winner

After simulating the game, check who is unable to make a move first. If Alice is unable to make the move, Bob wins. Otherwise, Alice wins. Ensure the simulation accounts for each player's turn and coin availability.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the approach chosen to simulate the game. If iterating through each turn and checking coin availability, the time complexity is O(min(x, y)), where x and y are the numbers of 75-value and 10-value coins respectively.

What Interviewers Usually Probe

Look for the candidate's ability to identify the constraints and break the problem into simpler steps like coin usage and turn simulation.
The candidate should be able to recognize the need for simulating the game turn by turn and handling coin depletion correctly.
Check if the candidate optimizes the solution by reducing unnecessary operations and understanding the constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the exact coin combination needed to make 115, leading to incorrect assumptions about game moves.
Not simulating each turn properly or missing conditions where a player cannot make a valid move.
Overcomplicating the solution by introducing unnecessary complexity rather than focusing on the simple simulation of each turn.

Follow-up variants

What if the coin values change but the sum remains 115?
How would the game change if players could take any number of coins per turn instead of just one 75-coin and four 10-coins?
What if players start with a different number of coins but still must form 115 in each turn?

FAQ

What is the optimal approach for solving the Find the Winning Player in Coin Game problem?

The optimal approach involves simulating each turn by deducting the necessary coins for each player, ensuring that both players play optimally with available coins.

How do I simulate the turns in the Coin Game?

Simulate each player's turn by subtracting one 75-coin and four 10-coins until a player cannot make a valid move, and then determine the winner.

What are the key constraints in the Coin Game problem?

The key constraints are that players must pick one 75-coin and four 10-coins per turn, and both players play optimally to win or lose based on available coins.

How does the Coin Game test my understanding of game theory?

The Coin Game tests your ability to simulate a game with optimal moves, emphasizing the strategy of taking turns and managing coin resources.

Can the Coin Game problem be solved by brute force?

Brute force is possible but inefficient; a better solution is to simulate the game optimally and consider the coin constraints to determine the winner.

terminal

Solution

Solution 1: Mathematics

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.

1

2

3

4

5

6

class Solution:
    def losingPlayer(self, x: int, y: int) -> str:
        k = min(x // 2, y // 8)
        x -= k * 2
        y -= k * 8
        return "Alice" if x and y >= 4 else "Bob"

Continue Practicing

#3227 vowels game in a string #3264 final array state after k multiplication operations i #3179 find the n th value after k seconds