Problem Description

You have two types of coins:

• x coins with value 75 each
• y coins with value 10 each

Alice and Bob play a turn-based game starting with Alice. In each turn, a player must pick up coins with a total value of exactly 115. The player who cannot make a valid move (cannot collect coins totaling 115) loses the game.

Both players play optimally, meaning they make the best possible moves to try to win.

Your task is to determine who wins the game and return the winner's name as a string ("Alice" or "Bob").

For example, to make a total of 115, a player could take:

• 1 coin of value 75 and 4 coins of value 10 (75 + 40 = 115)
• Any other valid combination that sums to exactly 115

The key insight is that since 115 = 75 + 40, and the only way to make 115 with these coin values is to use 1 coin of value 75 and 4 coins of value 10. However, you could also use different combinations like 0 coins of value 75 and 11.5 coins of value 10 (but since we need whole coins, this isn't valid), or explore if there are other valid combinations. Actually, checking the possibilities:

• Using 0 coins of 75: would need 115/10 = 11.5 coins of value 10 (not possible with whole coins)
• Using 1 coin of 75: would need (115-75)/10 = 4 coins of value 10 (valid)
• Using 2 or more coins of 75: would exceed 115 (since 2×75 = 150 > 115)

Therefore, each turn consumes exactly 1 coin of value 75 and 4 coins of value 10.

Intuition

Since each turn requires exactly 115 in total value, let's first figure out what combinations are possible with coins of value 75 and 10.

To make 115:

• If we use 0 coins of 75: we need 115/10 = 11.5 coins of 10 (impossible - not a whole number)
• If we use 1 coin of 75: we need (115-75)/10 = 4 coins of 10 (valid!)
• If we use 2 coins of 75: we get 2×75 = 150, which already exceeds 115 (impossible)

So the only valid combination is 1 coin of value 75 and 4 coins of value 10.

Now, since Alice goes first and players alternate, the winner depends on the total number of valid moves possible. If the total number of moves is odd, Alice wins (she makes the last valid move). If it's even, Bob wins.

How many rounds can be played? We're limited by whichever resource runs out first:

• We can use the 75-value coins for at most x rounds
• We can use the 10-value coins for at most y/4 rounds (since we need 4 per round)

Therefore, the maximum number of rounds is k = min(x, y/4).

After k complete rounds:

• Remaining 75-value coins: x - k
• Remaining 10-value coins: y - 4k

If k is even, it's Alice's turn again. She wins if she can make one more move (needs at least 1 coin of 75 and 4 coins of 10). Otherwise, Bob wins.

If k is odd, Bob just made the last complete move, so Alice wins.

The solution cleverly optimizes this by pairing up moves. Since each pair of moves uses 2 coins of 75 and 8 coins of 10, we can calculate pairs as k = min(x/2, y/8). After k pairs, if Alice can still make a move with the remaining coins, she wins; otherwise, Bob wins.

Learn more about Math patterns.

Solution Approach

The solution uses a mathematical approach to determine the winner efficiently without simulating the entire game.

Since each turn requires exactly 1 coin of value 75 and 4 coins of value 10, we can think about the game in terms of pairs of moves:

• Each pair of moves (2 turns) consumes 2 coins of value 75 and 8 coins of value 10
• After an even number of moves, it's Alice's turn again
• After an odd number of moves, it's Bob's turn

The implementation calculates how many complete pairs of moves can be made:

k = min(x // 2, y // 8)

This gives us the maximum number of move pairs possible, limited by whichever resource runs out first:

• x // 2: maximum pairs based on 75-value coins
• y // 8: maximum pairs based on 10-value coins

After k pairs of moves, we update the remaining coins:

x -= k * 2
y -= k * 8

Now, after k pairs (which means 2k total moves), it's Alice's turn again. The key decision point:

• If Alice can make another valid move (needs x >= 1 and y >= 4), she makes the (2k + 1)-th move and Bob cannot continue, so Alice wins
• If Alice cannot make a valid move, Bob wins since Alice is stuck

The condition x and y >= 4 checks if Alice has at least 1 coin of value 75 (x is truthy, meaning x > 0) and at least 4 coins of value 10 (y >= 4).

The return statement elegantly captures this logic:

return "Alice" if x and y >= 4 else "Bob"

This approach avoids simulating each individual turn and directly computes the game outcome in O(1) time with O(1) space.

Example Walkthrough

Let's walk through an example with x = 5 coins of value 75 and y = 20 coins of value 10.

Step 1: Calculate maximum pairs of moves

• Each pair of moves uses 2 coins of value 75 and 8 coins of value 10
• Maximum pairs based on 75-value coins: 5 // 2 = 2 pairs
• Maximum pairs based on 10-value coins: 20 // 8 = 2 pairs
• So k = min(2, 2) = 2 pairs can be played

Step 2: Simulate the pairs

• Pair 1 (Moves 1-2):
  • Alice's move: Takes 1×75 + 4×10 = 115. Remaining: 4×75, 16×10
  • Bob's move: Takes 1×75 + 4×10 = 115. Remaining: 3×75, 12×10
• Pair 2 (Moves 3-4):
  • Alice's move: Takes 1×75 + 4×10 = 115. Remaining: 2×75, 8×10
  • Bob's move: Takes 1×75 + 4×10 = 115. Remaining: 1×75, 4×10

Step 3: Check if Alice can make another move After 2 pairs (4 total moves), it's Alice's turn again with:

• Remaining 75-value coins: x = 5 - (2 × 2) = 1
• Remaining 10-value coins: y = 20 - (2 × 8) = 4

Alice needs at least 1 coin of value 75 and 4 coins of value 10 to make a valid move.

• She has exactly 1×75 and 4×10, so she CAN make move #5
• After Alice's 5th move: 0×75, 0×10 remaining
• Bob cannot make a valid move (no coins left)

Result: Alice wins!

This matches our formula: After k=2 pairs, we have x=1 and y=4, so the condition x and y >= 4 is true (1 is truthy and 4 >= 4), returning "Alice".

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the code performs a fixed number of arithmetic operations regardless of the input size. The operations include:

• Computing min(x // 2, y // 8) - constant time
• Two subtraction operations x -= k * 2 and y -= k * 8 - constant time
• A conditional check x and y >= 4 - constant time
• Returning a string - constant time

The space complexity is O(1) because the algorithm only uses a constant amount of extra space. The only additional variable created is k, which stores a single integer value. No data structures that grow with input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Turn Calculation Logic

Pitfall: A common mistake is thinking that after k pairs of moves (2k total moves), it's Bob's turn instead of Alice's turn. This leads to reversing the winner logic.

Why it happens: The confusion arises from not carefully tracking whose turn it is after an even number of moves. Remember:

• After 0 moves: Alice's turn
• After 1 move: Bob's turn
• After 2 moves: Alice's turn
• After 3 moves: Bob's turn
• After 2k moves: Alice's turn

Solution: Always remember that Alice starts first, so after any even number of moves, it's Alice's turn again.

2. Incorrect Move Validation

Pitfall: Using x >= 1 and y >= 4 instead of x and y >= 4 (or equivalently x > 0 and y >= 4).

Why it's problematic: While both work in this case, the original code uses Python's truthy/falsy behavior where x evaluates to False when x == 0. Some developers might "correct" this to x >= 1 thinking it's clearer, but then accidentally write something like x >= 1 or y >= 4 (using OR instead of AND), which would be incorrect.

Solution: Be consistent and clear with your boolean logic. Either use:

if remaining_x >= 1 and remaining_y >= 4:

or

if remaining_x > 0 and remaining_y >= 4:

3. Overcomplicated Game Simulation

Pitfall: Attempting to simulate the entire game turn by turn:

def losingPlayer(self, x: int, y: int) -> str:
    turn = 0
    while x >= 1 and y >= 4:
        x -= 1
        y -= 4
        turn += 1
    return "Bob" if turn % 2 == 1 else "Alice"

Why it's problematic: While this works, it's inefficient with O(min(x, y/4)) time complexity when the mathematical approach achieves O(1).

Solution: Recognize the pattern that every 2 moves consume fixed resources (2 coins of 75, 8 coins of 10), allowing you to calculate the outcome directly without simulation.

4. Integer Division Confusion

Pitfall: Not understanding why we use min(x // 2, y // 8) for complete pairs instead of checking individual moves.

Why it matters: Each pair of moves requires exactly 2 coins of value 75 and 8 coins of value 10. We must ensure both resources are sufficient for complete pairs. Using min(x, y // 4) would count individual moves but wouldn't properly account for pairs.

Solution: Always think in terms of complete pairs (2 moves) first, then check if one additional move is possible. This simplifies the logic and ensures correct turn attribution.