Find the Winning Player in Coin Game — Problem & Solution
Find the Winning Player in Coin Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find the Winning Player in Coin Game is an easy coding problem on math and game theory, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Math, Game Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are x coins worth 75 each and y coins worth 10 each. Alice and Bob take turns, Alice going first.
On a turn a player must remove coins with a total value of exactly 115 — one 75-coin and four 10-coins. A player who cannot do this loses.
Return the name of the player who wins, assuming optimal play.
Example 1
Input: x = 2, y = 7
Output: Alice
Explanation: One full turn is possible: Alice takes it, then Bob cannot move.
Example 2
Input: x = 4, y = 11
Output: Bob
Explanation: Two turns are possible, so Alice runs out first.
Example 3
Input: x = 1, y = 2
Output: Bob
Explanation: Alice cannot even make the first move.
Constraints
1 <= x, y <= 100
Hints for Find the Winning Player in Coin Game
Hint 1
Every turn is identical: exactly one 75-coin and exactly four 10-coins.
Hint 2
So the total number of turns is fixed at
min(x, y / 4)— there are no real choices.Hint 3
Alice moves on the odd-numbered turns, so she wins exactly when that count is odd.
How to solve Find the Winning Player in Coin Game
There is only one way to make 115 from coins of 75 and 10 — one and four — so the game has no branching. The winner follows from the parity of the fixed turn count.
Approach
- Compute
turns = min(x, y / 4)using integer division. - Return
"Alice"whenturnsis odd,"Bob"when it is even.
Why it works
75a + 10b = 115 with non-negative integers forces a = 1, b = 4: a = 0 needs b = 11.5, and a >= 2 already overshoots. So each turn consumes exactly one 75-coin and four 10-coins, and play stops after min(x, y/4) turns. The player to move when no turn remains loses, which is Bob exactly when the count is odd.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Assuming a player could take two 75-coins (150) or eleven 10-coins overcomplicates a game with a single legal move.
turns = 0means Alice cannot move at all, so Bob wins — which the even branch already covers.
Reference solution
Python
def losingPlayer(x: int, y: int) -> str:
turns = min(x, y // 4)
return "Alice" if turns % 2 == 1 else "Bob"Java
public static String losingPlayer(int x, int y) {
int turns = Math.min(x, y / 4);
return turns % 2 == 1 ? "Alice" : "Bob";
}C++
string losingPlayer(int x, int y) {
int turns = min(x, y / 4);
return turns % 2 == 1 ? "Alice" : "Bob";
}JavaScript
var losingPlayer = function(x, y) {
const turns = Math.min(x, Math.floor(y / 4));
return turns % 2 === 1 ? "Alice" : "Bob";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.