Find the Winning Player in Coin Game

EASY

Description

You are given two positive integers x and y, denoting the number of coins with values 75 and 10 respectively.

Alice and Bob are playing a game. Each turn, starting with Alice, the player must pick up coins with a total value 115. If the player is unable to do so, they lose the game.

Return the name of the player who wins the game if both players play optimally.

Example 1:

Input: x = 2, y = 7

Output: "Alice"

Explanation:

The game ends in a single turn:

Alice picks 1 coin with a value of 75 and 4 coins with a value of 10.

Example 2:

Input: x = 4, y = 11

Output: "Bob"

Explanation:

The game ends in 2 turns:

Alice picks 1 coin with a value of 75 and 4 coins with a value of 10.
Bob picks 1 coin with a value of 75 and 4 coins with a value of 10.

Constraints:

1 <= x, y <= 100

Approaches

Checkout 2 different approaches to solve Find the Winning Player in Coin Game. Click on different approaches to view the approach and algorithm in detail.

Iterative Simulation of the Game

This approach directly simulates the game turn by turn. We maintain the current count of each type of coin and a turn counter. In each step, we check if a move is possible. A move consists of using one 75-value coin and four 10-value coins. If a move can be made, we decrement the coin counts and increment the turn counter. The game ends when a move is no longer possible. The winner is determined by the parity of the total number of turns played.

Algorithm

Initialize a variable turns to 0 to count the number of successful moves.
Start a while loop that continues as long as there are enough coins for a move, i.e., x >= 1 and y >= 4.
Inside the loop, simulate a single turn:
- Decrement x by 1.
- Decrement y by 4.
- Increment the turns counter by 1.
The loop terminates when a player can no longer make a move.
After the loop, check the parity of the turns variable.
If turns is odd, it means Alice made the last possible move. Thus, Alice wins.
If turns is even (including 0), it means either Bob made the last move or no moves were possible at all. In either case, Bob wins.

The core idea is to model the game flow. Alice starts first. We use a loop that continues as long as the current player has enough coins to make a move (at least one 75-coin and four 10-coins). Inside the loop, we simulate one turn by decrementing the coin counts (x by 1, y by 4) and tracking the total number of turns. The loop terminates when x < 1 or y < 4. At this point, no more moves can be made. The total number of turns completed determines the winner. If the total number of turns is odd, it means Alice made the last move, and Bob is now unable to move, so Alice wins. If the total number of turns is even (or zero), it means either Bob made the last move or no moves were possible at all, so Bob wins.

class Solution {
    public String losingPlayer(int x, int y) {
        int turns = 0;
        // Keep playing turns as long as possible
        while (x >= 1 && y >= 4) {
            x -= 1;
            y -= 4;
            turns++;
        }
        
        // Alice wins if the total number of turns is odd.
        // Bob wins if the total number of turns is even (or zero).
        if (turns % 2 == 1) {
            return "Alice";
        } else {
            return "Bob";
        }
    }
}

Complexity Analysis

Time Complexity: O(min(x, y/4)). The number of iterations in the while loop is equal to the total number of turns possible, which is limited by the minimum of `x` and `y/4`.Space Complexity: O(1) because it only uses a few variables to store the state, regardless of the input size.

Pros and Cons

Pros:

It is intuitive and easy to understand as it directly follows the rules of the game.
It is guaranteed to be correct and is efficient enough for the given constraints.

Cons:

It is less efficient than a direct mathematical approach as it involves a loop.
For much larger constraints on x and y, this approach could be too slow, whereas a mathematical solution would remain constant time.

Code Solutions

Checking out 3 solutions in different languages for Find the Winning Player in Coin Game. Click on different languages to view the code.

class Solution {
public
  String losingPlayer(int x, int y) {
    int k = Math.min(x / 2, y / 8);
    x -= k * 2;
    y -= k * 8;
    return x > 0 && y >= 4 ? "Alice" : "Bob";
  }
}

Video Solution

Watch the video walkthrough for Find the Winning Player in Coin Game

Patterns:

MathGame Theory