Difficulty: Easy | Acceptance: 53.30% | Paid: No Topics: Math, Simulation, Game Theory
You are given two integers x and y representing the number of coins in two piles. Alice has x coins and Bob has y coins. Alice starts the game.
In each turn, a player removes 2, 3, or 5 coins from the pile they choose. The player who cannot make a move loses.
Return “Alice” if Alice wins, otherwise “Bob”.
- Examples
- Constraints
- Mathematical Analysis
- Simulation
Examples
Input: x = 2, y = 7
Output: "Bob"
Explanation:
- Alice's turn: She has 2 coins. She removes 2 coins. Now she has 0 coins.
- Bob's turn: He has 7 coins. He removes 2 coins. Now he has 5 coins.
- Alice's turn: She has 0 coins. She cannot make a move. She loses.
Bob wins.
Input: x = 4, y = 11
Output: "Bob"
Explanation:
- Alice's turn: She has 4 coins. She removes 2 coins. Now she has 2 coins.
- Bob's turn: He has 11 coins. He removes 2 coins. Now he has 9 coins.
- Alice's turn: She has 2 coins. She removes 2 coins. Now she has 0 coins.
- Bob's turn: He has 9 coins. He removes 2 coins. Now he has 7 coins.
- Alice's turn: She has 0 coins. She cannot make a move. She loses.
Bob wins.
Constraints
1 <= x, y <= 100
Mathematical Analysis
Intuition The game is determined by who can make more moves. Since players play optimally to win, they will maximize the number of turns they can survive. The minimum number of coins a player can remove in a turn is 2. Therefore, to maximize the number of moves, a player should always remove exactly 2 coins. The player with the larger number of possible moves (integer division of coins by 2) will be the one to make the last move, causing the opponent to run out of moves first.
Steps
- Calculate the maximum number of moves Alice can make:
moves_x = x // 2. - Calculate the maximum number of moves Bob can make:
moves_y = y // 2. - If
moves_x > moves_y, Alice makes the last move and Bob runs out of coins first. Return “Alice”. - Otherwise, Bob makes the last move (or Alice runs out first). Return “Bob”.
Complexity
- Time: O(1)
- Space: O(1)
- Notes: This is the most optimal approach with constant time complexity.
Simulation
Intuition We can simulate the game process turn by turn. Alice starts first. In each turn, the current player removes 2 coins (optimal play) from their own pile. If a player cannot remove 2 coins (i.e., has fewer than 2 coins), they lose.
Steps
- Loop indefinitely.
- Check if Alice has fewer than 2 coins. If so, she loses, return “Bob”.
- Alice removes 2 coins from her pile.
- Check if Bob has fewer than 2 coins. If so, he loses, return “Alice”.
- Bob removes 2 coins from his pile.
Complexity
- Time: O(x + y) in the worst case, as we iterate until one pile is empty.
- Space: O(1)
- Notes: While intuitive, this approach is less efficient than the mathematical solution but perfectly valid given the constraints.