Find the Winning Player in Coin Game

Easy
561.

Find the Winning Player in Coin Game

Find the Winning Player in Coin Game is an easy coding problem on math and game theory, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} x
 * @param {number} y
 * @return {string}
 */
var losingPlayer = function(x, y) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Every turn is identical: exactly one 75-coin and exactly four 10-coins.

  2. Hint 2

    So the total number of turns is fixed at min(x, y / 4) — there are no real choices.

  3. 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

  1. Compute turns = min(x, y / 4) using integer division.
  2. Return "Alice" when turns is 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 = 0 means 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.

All 337 math problems · the whole catalogue