LeetCode 3222 - Find the Winning Player in Coin Game

LeetCode Problem 3222

Difficulty: 🟢 Easy
Topics: Math, Simulation, Game Theory

Solution

Problem Understanding

The game gives us two types of coins:

• x coins worth 75
• y coins worth 10

Two players, Alice and Bob, take turns. Alice always moves first. On every turn, the current player must select coins whose total value is exactly 115. If a player cannot make such a move, that player loses immediately.

We need to determine which player wins if both play optimally.

The first step is understanding how a valid move can be formed. Since the available coin values are only 75 and 10, we need to solve:

$$75a + 10b = 115$$

where a and b are non-negative integers.

Trying possible values quickly shows that the only valid combination is:

$$75 \times 1 + 10 \times 4 = 115$$

So every move always consumes:

• exactly 1 coin worth 75
• exactly 4 coins worth 10

This simplifies the entire game dramatically. Instead of exploring many move possibilities, every turn is forced.

The number of total moves possible is therefore limited by:

• how many 75 coins exist
• how many groups of four 10 coins exist

The total number of turns that can be played is:

$$\min(x,\ y // 4)$$

If the number of turns is odd, Alice makes the final move and Bob cannot continue, so Alice wins.

If the number of turns is even, Bob makes the final move and Alice cannot continue, so Bob wins.

The constraints are very small, 1 <= x, y <= 100, which means even simulation would work comfortably. However, the problem has a direct mathematical solution that runs in constant time.

Important edge cases include situations where there are not enough 10 coins to complete even one move, or where one resource runs out before the other. For example, having many 75 coins is useless if there are fewer than four 10 coins.

Approaches

Brute Force Approach

A brute force simulation would repeatedly perform valid moves until one player cannot continue.

At each turn:

1. Check whether at least one 75 coin and four 10 coins remain.
2. If yes, remove those coins.
3. Alternate the current player.
4. Continue until a move is impossible.

This approach is correct because the game has only one legal move configuration. By simulating every turn exactly as the game rules specify, we eventually reach the terminal state where one player cannot move.

Although this works efficiently for the given constraints, it still performs unnecessary iteration because the number of turns can be computed directly.

Optimal Approach

The key observation is that every move is forced:

$$115 = 75 + 10 + 10 + 10 + 10$$

No other combination exists.

That means each turn consumes:

• 1 seventy-five coin
• 4 ten-value coins

Therefore, the total number of moves possible is simply:

$$\text{moves} = \min(x,\ y // 4)$$

The winner depends only on whether this count is odd or even:

• odd number of moves, Alice wins
• even number of moves, Bob wins

This avoids simulation entirely and gives a constant time solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(min(x, y/4))	O(1)	Simulates each turn until no move remains
Optimal	O(1)	O(1)	Directly computes total playable turns

Algorithm Walkthrough

1. Compute how many complete moves can be performed using the 10 value coins.

Since each move requires four 10 coins, the number of moves supported by these coins is:

y // 4

2. Compute how many complete moves can be performed using the 75 value coins.

Each move requires exactly one 75 coin, so the number of moves supported by these coins is:

x

3. The actual number of playable turns is the smaller of these two values.

moves = min(x, y // 4)

This works because a move cannot happen unless both resources are available simultaneously. 4. Determine whose turn would be the last valid move.

Alice moves first.

• If moves is odd, Alice takes the final move and Bob loses.
• If moves is even, Bob takes the final move and Alice loses.

5. Return the corresponding winner string.

Why it works

Every legal move consumes the exact same resources, one 75 coin and four 10 coins. Because the game has no branching decisions, the entire game state is determined solely by how many such move bundles exist. The player making the final valid move wins, so the parity of the total move count completely determines the answer.

Python Solution

class Solution:
    def winningPlayer(self, x: int, y: int) -> str:
        moves = min(x, y // 4)

        if moves % 2 == 1:
            return "Alice"

        return "Bob"

The implementation starts by computing the total number of valid turns possible. Since every move consumes one 75 coin and four 10 coins, the limiting factor is whichever resource runs out first.

The expression y // 4 calculates how many complete groups of four 10 coins are available. Taking the minimum with x gives the exact number of turns the game can last.

After that, the code checks whether the move count is odd or even. Because Alice always plays first, odd counts mean Alice takes the final turn, while even counts mean Bob does.

The solution uses only a few integer operations and no extra data structures.

Go Solution

func winningPlayer(x int, y int) string {
    moves := min(x, y/4)

    if moves%2 == 1 {
        return "Alice"
    }

    return "Bob"
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go implementation follows the exact same logic as the Python version. One small difference is that Go does not provide a built-in integer min function for older versions, so we define our own helper function.

Integer division in Go automatically truncates toward zero, so y / 4 correctly computes the number of complete four-coin groups.

Since the constraints are tiny, integer overflow is not a concern.

Worked Examples

Example 1

Input:

x = 2
y = 7

First compute the number of possible moves:

Calculation	Value
y // 4	7 // 4 = 1
min(x, y // 4)	min(2, 1) = 1

So only one move can occur.

Game simulation:

Turn	Player	Coins Used	Remaining (x, y)
1	Alice	1 x 75, 4 x 10	(1, 3)

Now Bob cannot make another move because only three 10 coins remain.

Since the total number of moves is odd, Alice wins.

Output:

"Alice"

Example 2

Input:

x = 4
y = 11

Compute possible moves:

Calculation	Value
y // 4	11 // 4 = 2
min(x, y // 4)	min(4, 2) = 2

So exactly two moves can occur.

Game simulation:

Turn	Player	Coins Used	Remaining (x, y)
1	Alice	1 x 75, 4 x 10	(3, 7)
2	Bob	1 x 75, 4 x 10	(2, 3)

Now Alice cannot continue because only three 10 coins remain.

Since the total number of moves is even, Bob wins.

Output:

"Bob"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	No extra memory or data structures are used

The algorithm does not depend on the size of the input values beyond basic arithmetic. Regardless of how large x and y become, the solution performs the same constant amount of work.

Test Cases

solution = Solution()

assert solution.winningPlayer(2, 7) == "Alice"  # Provided example, one move
assert solution.winningPlayer(4, 11) == "Bob"   # Provided example, two moves

assert solution.winningPlayer(1, 4) == "Alice"  # Exactly one valid move
assert solution.winningPlayer(2, 8) == "Bob"    # Exactly two valid moves
assert solution.winningPlayer(3, 12) == "Alice" # Exactly three valid moves

assert solution.winningPlayer(10, 3) == "Bob"   # Not enough 10-value coins
assert solution.winningPlayer(1, 100) == "Alice" # Limited by 75-value coins
assert solution.winningPlayer(100, 4) == "Alice" # Only one move possible

assert solution.winningPlayer(100, 100) == "Bob" # min(100, 25) = 25, Alice wins
assert solution.winningPlayer(100, 96) == "Bob"  # min(100, 24) = 24, Bob wins

assert solution.winningPlayer(5, 20) == "Alice"  # Odd number of moves
assert solution.winningPlayer(6, 24) == "Bob"    # Even number of moves

Test Summary

Test	Why
(2, 7)	Validates the first sample
(4, 11)	Validates the second sample
(1, 4)	Minimum resources for one move
(2, 8)	Tests even move count
(3, 12)	Tests odd move count
(10, 3)	Not enough 10 coins
(1, 100)	Limited by 75 coins
(100, 4)	Only one move possible despite many 75 coins
(100, 100)	Large balanced input
(100, 96)	Large even move count
(5, 20)	Another odd parity case
(6, 24)	Another even parity case

Edge Cases

One important edge case occurs when there are not enough 10 coins to complete even one move. For example, x = 10 and y = 3. Even though there are many 75 coins available, a move requires four 10 coins, so the game cannot start. The implementation handles this naturally because y // 4 becomes 0, making the total move count zero and correctly declaring Bob as the winner.

Another important case happens when there are plenty of 10 coins but very few 75 coins. For example, x = 1 and y = 100. A naive solution might incorrectly assume many moves are possible because of the large number of 10 coins. However, each move also requires one 75 coin, so only one move can happen. Using min(x, y // 4) correctly limits the move count to one.

A third edge case involves parity. The entire result depends on whether the total move count is odd or even. For example, x = 6 and y = 24 allows exactly six moves, which is even, so Bob wins. A common mistake is incorrectly mapping odd and even counts to players. The implementation avoids this by explicitly checking moves % 2 == 1 for Alice's victory.