Find the Winning Player in Coin Game solution and explanation
7 more videos on this problem
3222. Find the Winning Player in Coin Game (Leetcode Easy)Programming Live with Larry · 3:53 · 506 views
3222. Find the Winning Player in Coin Game | Simulation | MathTech Courses · 5:37 · 410 views
leetcode 3222: coin game winner : python solutionleetcode blind 75 · 5:19 · 292 views
3222. Find the Winning Player in Coin Game (leetcode easy)Coder on A Farm · 3:41 · 168 views
Find the winning player in coin game |LeetcodeBrute force · 3:55 · 107 views
Leetcode 3222 Find the Winning Player in Coin GameAlgorithmicIQ · 8:18 · 71 views
Leetcode 3222: Find the Winning Player in Telugu | Optimal approach | Python DSA | srkcodesSrk Codes · 6:42 · 66 views
Leetcode Biweekly Contest 135 | Find the winning player in coin game | O(1) SolutionAuctus With Us · 6:36 · 50 views
The 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
Approach overview
Problem Overview: Two players take turns performing a fixed operation on two coin piles. Each move removes 1 coin from the first pile and 4 coins from the second pile. The player who cannot make a valid move loses. Given the number of coins in both piles, determine which player wins assuming optimal play.
Approach 1: Simulation (O(k) time, O(1) space)
The most direct way is to simulate the game. As long as the piles allow a move (x >= 1 and y >= 4), subtract 1 from the first pile and 4 from the second. Track whose turn it is and flip the turn after each move. When the loop stops, the player who was supposed to move next loses, so the previous player wins.
This method models the game exactly and is useful for understanding the mechanics. However, the number of iterations equals the number of valid moves. That value can be derived mathematically, which leads to a more efficient approach. This reasoning pattern appears frequently in simulation and simple game theory problems.
Approach 2: Greedy / Mathematical Insight (O(1) time, O(1) space)
Every move always consumes the same resources: 1 coin from pile x and 4 coins from pile y. That means the total number of moves possible in the entire game is limited by whichever pile runs out first. The exact number of valid moves is k = min(x, y // 4).
Once k is known, the winner becomes a simple parity check. Alice starts the game, so if the total number of moves is odd, Alice performs the final move and wins. If the number of moves is even, Bob performs the final move and wins. This converts the problem into a constant-time calculation using basic math reasoning.
This greedy observation removes the need for simulation entirely. Instead of iterating through moves, you directly compute the maximum possible turns and determine which player gets the last one.
Recommended for interviews: The mathematical greedy approach is the expected solution. It demonstrates that you recognized the fixed resource consumption per move and reduced the game to a parity check. Explaining the simulation first shows understanding of the rules, but deriving k = min(x, y // 4) and checking odd/even shows stronger problem-solving skills.
Approach 1: Greedy Approach
The crucial part of the problem is ensuring a player can pick coins totaling 115 on each turn. A greedy approach can be useful, where we first attempt to use as many 75-value coins as needed, and then adjust with 10-value coins if possible.
For each turn, check if it's possible to pick coins to make 115. If the current player can't make a move, they lose the game. Start with the optimal strategy for Alice using available coins with the highest value first (75-value coins).
def find_winner(x, y):
while x > 0 or y >= 11:
if x > 0 and y >= 4:
x -= 1
y -= 4
elif y >= 11:
y -= 11
else:
break
return 'Bob' if x <= 0 and y < 4 else 'Alice'
# Example usage
x, y = 2, 7
print(find_winner(x, y))public class CoinGame {
public static String findWinner(int x, int y) {
while (x > 0 || y >= 11) {
if (x > 0 && y >= 4) {
x--;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
}
return x <= 0 && y < 4 ? "Bob" : "Alice";
}
public static void main(String[] args) {
int x = 2, y = 7;
System.out.println(findWinner(x, y));
}
}#include <iostream>
using namespace std;
string findWinner(int x, int y) {
while (x > 0 || y >= 11) {
if (x > 0 && y >= 4) {
x--;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
}
return (x <= 0 && y < 4) ? "Bob" : "Alice";
}
int main() {
int x = 2, y = 7;
cout << findWinner(x, y) << endl;
return 0;
}function findWinner(x, y) {
while (x > 0 || y >= 11) {
if (x > 0 && y >= 4) {
x -= 1;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
}
return x <= 0 && y < 4 ? "Bob" : "Alice";
}
// Example usage
let x = 2, y = 7;
console.log(findWinner(x, y));#include <stdio.h>
const char* findWinner(int x, int y) {
while (x > 0 || y >= 11) {
// Try to use one 75 coin first, then the remaining with 10 value coins
if (x > 0 && y >= 4) {
x -= 1;
y -= 4;
} else if (y >= 11) { // Otherwise try with only 10 value coins
y -= 11;
} else {
break; // Not possible to make 115 with current coins
}
// Flip the player until no moves are left
}
return x <= 0 && y < 4 ? "Bob" : "Alice";
}
int main() {
int x = 2, y = 7;
printf("%s\n", findWinner(x, y));
return 0;
}using System;
class Program {
public static string FindWinner(int x, int y) {
while (x > 0 || y >= 11) {
if (x > 0 && y >= 4) {
x--;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
}
return x <= 0 && y < 4 ? "Bob" : "Alice";
}
static void Main() {
int x = 2, y = 7;
Console.WriteLine(FindWinner(x, y));
}
}In Python, the implementation uses the greedy strategy to manage coins optimally for players to achieve a cumulative total of 115. Priority checks are made for reducing 75 coins, adjusting with 10s as needed, and maintaining turns until no profitable moves are open, designating the winner before breaks.
Given fixed maximum constraints from the problem definition: Time complexity: O(1).
Space complexity: O(1).
Approach 2: Simulation Approach
Instead of a greedy approach, this simulation method iteratively reflects each player's move, step-by-step adjusting coins down in realistic gameplay. Each turn is evaluated in depth for potential coin uses, ensuring the players toggle turns by confirming progress within permissible moves made by previous players.
Each move by Alice and Bob factors in various combinations to make a sum with available coins and determines if progress is possible. A general game simulation allows understanding of transition from one turn to the next when playing optimally, and chiseling down until one player can no longer form 115.
def find_winner(x, y):
turn = 0 # 0 for Alice, 1 for Bob
while True:
if x > 0 and y >= 4:
x -= 1
y -= 4
elif y >= 11:
y -= 11
else:
break
turn ^= 1
return 'Bob' if turn == 0 else 'Alice'
# Example usage
print(find_winner(2, 7))public class CoinGameSimulation {
public static String findWinner(int x, int y) {
int turn = 0; // 0 for Alice, 1 for Bob
while (true) {
if (x > 0 && y >= 4) {
x--;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
turn ^= 1; // Switch turns
}
return turn == 0 ? "Bob" : "Alice";
}
public static void main(String[] args) {
System.out.println(findWinner(2, 7));
}
}#include <iostream>
using namespace std;
string findWinner(int x, int y) {
int turn = 0; // Even for Alice, Odd for Bob
while (true) {
if (x > 0 && y >= 4) {
x -= 1;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
turn ^= 1; // Bitwise toggle to switch turns
}
return (turn == 0) ? "Bob" : "Alice";
}
int main() {
cout << findWinner(2, 7) << endl;
return 0;
}function findWinner(x, y) {
let turn = 0; // 0 for Alice, 1 for Bob
while (true) {
if (x > 0 && y >= 4) {
x -= 1;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
turn ^= 1;
}
return turn === 0 ? "Bob" : "Alice";
}
console.log(findWinner(2, 7));#include <stdio.h>
const char* findWinner(int x, int y) {
int turn = 0; // Alice starts with turn 0, Bob with turn 1
while (1) {
if (x > 0 && y >= 4) {
x--;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
turn ^= 1; // Toggle between 0 and 1 to switch player
}
return turn == 0 ? "Bob" : "Alice";
}
int main() {
int x = 2, y = 7;
printf("%s\n", findWinner(x, y));
return 0;
}using System;
class SimulationGame {
public static string FindWinner(int x, int y) {
int turn = 0; // 0 = Alice, 1 = Bob
while (true) {
if (x > 0 && y >= 4) {
x -= 1;
y -= 4;
} else if (y >= 11) {
y -= 11;
} else {
break;
}
turn ^= 1;
}
return turn == 0 ? "Bob" : "Alice";
}
static void Main() {
Console.WriteLine(FindWinner(2, 7));
}
}By adopting a simulation approach in Python, the solution iterates through moves using toggles to manifest sequence of combined decisions. Each player takes turns checked through constraints within a realistic gameplay model.
This simulation encapsulates exhaustive checks of coin matches until it stops, inferring the player last unable to act as the loser.
Enjoying general complexity constants: Time complexity: O(1).
Space complexity: O(1).
Approach 3: Mathematics
Since each round of operation consumes 2 coins valued at 75 and 8 coins valued at 10, we can calculate the number of rounds k = min(x / 2, y / 8), and then update the values of x and y, where x and y are the remaining number of coins after k rounds of operations.
If x > 0 and y geq 4, then Alice can continue the operation, and Bob loses, return "Alice"; otherwise, return "Bob".
The time complexity is O(1), and the space complexity is O(1).
function losingPlayer(x: number, y: number): string {
const k = Math.min((x / 2) | 0, (y / 8) | 0);
x -= k * 2;
y -= k * 8;
return x && y >= 4 ? 'Alice' : 'Bob';
}func losingPlayer(x int, y int) string {
k := min(x/2, y/8)
x -= 2 * k
y -= 8 * k
if x > 0 && y >= 4 {
return "Alice"
}
return "Bob"
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Given fixed maximum constraints from the problem definition: Time complexity: O(1). |
| Simulation Approach | Enjoying general complexity constants: Time complexity: O(1). |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation | O(k) | O(1) | When modeling the game step-by-step to understand turn mechanics |
| Greedy / Mathematical Insight | O(1) | O(1) | Best choice when each move consumes fixed resources and total moves can be computed directly |
Frequently asked questions
Is Find the Winning Player in Coin Game easy or hard?
Find the Winning Player in Coin Game is classified as an Easy problem. Once you notice that each move consumes a fixed number of coins, the game reduces to counting the total possible moves and checking whether that number is odd or even.
Find the Winning Player in Coin Game Python/Java solution
The implementation is very small in Python or Java. Calculate k = min(x, y // 4) and return "Alice" if k % 2 == 1, otherwise return "Bob". The logic is identical across languages since it only involves arithmetic operations.
How to solve Find the Winning Player in Coin Game in O(1)?
Compute the maximum number of valid moves as k = min(x, y // 4). Since players alternate turns starting with Alice, the winner depends on the parity of k. If k is odd, Alice performs the last move and wins; if k is even, Bob wins.
What is the best approach for Find the Winning Player in Coin Game?
The optimal solution uses a greedy mathematical observation. Each move removes 1 coin from the first pile and 4 coins from the second, so the total number of possible moves is min(x, y // 4). If this count is odd, Alice wins; if it is even, Bob wins. This approach runs in O(1) time and O(1) space.
Is Find the Winning Player in Coin Game asked at Google/Amazon/Meta?
Problems based on simple game theory and parity analysis are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of reducing a turn-based game to a mathematical observation appears frequently.
What data structure is used in Find the Winning Player in Coin Game?
No complex data structure is required. The solution relies on basic arithmetic operations and a parity check. The problem mainly tests math reasoning and game theory rather than data structure usage.
What is the time complexity of Find the Winning Player in Coin Game?
The optimal solution runs in O(1) time because it only computes min(x, y // 4) and checks whether the result is odd or even. A direct simulation approach would take O(k) time where k is the number of possible moves.