# Find the Winning Player in Coin Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-winning-player-in-coin-game)
Canonical: https://scaleengineer.com/dsa/problems/find-the-winning-player-in-coin-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
---
## Problem
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
## 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.
**Time:** 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:** O(1) because it only uses a few variables to store the state, regardless of the input size.
**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.
### Explanation
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.

```java
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";
        }
    }
}
```
### Algorithm
1. Initialize a variable `turns` to 0 to count the number of successful moves.
2. Start a `while` loop that continues as long as there are enough coins for a move, i.e., `x >= 1` and `y >= 4`.
3. Inside the loop, simulate a single turn:
   - Decrement `x` by 1.
   - Decrement `y` by 4.
   - Increment the `turns` counter by 1.
4. The loop terminates when a player can no longer make a move.
5. After the loop, check the parity of the `turns` variable.
6. If `turns` is odd, it means Alice made the last possible move. Thus, Alice wins.
7. 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.

## Direct Mathematical Calculation
A more efficient approach involves analyzing the game's structure to find a direct mathematical solution. The key observation is that there is only one possible move: taking one 75-value coin and four 10-value coins. This makes the game deterministic. The total number of turns is limited by the resource that runs out first. By calculating the maximum possible turns directly, we can determine the winner in constant time.
**Time:** O(1) because the solution involves a fixed number of arithmetic operations (division, min, modulo), regardless of the input values `x` and `y`. · **Space:** O(1) as no additional space that scales with the input is required.
**Pros:** Extremely efficient, providing an instant answer with constant time complexity.; The solution is elegant and concise.; It is scalable and would work even with much larger input values for `x` and `y`.
**Cons:** Requires a preliminary analysis of the game to derive the mathematical formula, which might be less immediately obvious than simulation.
### Explanation
First, we must identify the components of a single move. To make a sum of 115 with 75s and 10s, the only combination is `1 * 75 + 4 * 10 = 115`. Therefore, each turn consumes exactly one 75-coin and four 10-coins. The game can continue as long as there are enough coins for a move. The number of moves is constrained by both `x` (the number of 75-coins) and `y` (the number of 10-coins). The maximum number of turns supportable by the 75-coins is `x`. The maximum number of turns supportable by the 10-coins is `y / 4` (using integer division, as we need 4 coins per turn). The actual number of turns that can be played is the minimum of these two values: `total_turns = min(x, y / 4)`. Since Alice starts, she takes turns 1, 3, 5, ... and Bob takes turns 2, 4, 6, ... . If the `total_turns` is an odd number, Alice will take the last turn and win. If `total_turns` is an even number (or zero), Bob will either take the last turn or Alice won't be able to move at all, so Bob wins.

```java
class Solution {
    public String losingPlayer(int x, int y) {
        // Calculate the maximum number of turns possible.
        // A turn requires 1 coin of value 75 and 4 coins of value 10.
        int possibleTurns = Math.min(x, y / 4);
        
        // If the number of turns is odd, Alice wins. Otherwise, Bob wins.
        return (possibleTurns % 2 == 1) ? "Alice" : "Bob";
    }
}
```
### Algorithm
1. First, determine the only possible move. To make a sum of 115 with 75s and 10s, the only combination of non-negative integers is `1 * 75 + 4 * 10 = 115`.
2. Realize that each turn is fixed and consumes one 75-coin and four 10-coins.
3. The total number of turns is limited by the resource that runs out first.
4. Calculate the number of turns possible given `x` 75-coins, which is `x`.
5. Calculate the number of turns possible given `y` 10-coins, which is `y / 4` (using integer division).
6. The actual total number of turns in the game is `total_turns = min(x, y / 4)`.
7. Since Alice and Bob play alternately, the winner depends on the parity of `total_turns`.
8. If `total_turns` is odd, Alice takes the last turn and wins.
9. If `total_turns` is even or zero, Bob wins.

# Solutions
### Java

```java
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";
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def losingPlayer(self, x: int, y: int) -> str: k = min(x // 2, y // 8) x -= k * 2 y -= k * 8 return "Alice" if x and y >= 4 else "Bob"

```